- Tytuł:
- On the independence number of edge chromatic critical graphs
- Autorzy:
-
Pang, Shiyou
Miao, Lianying
Song, Wenyao
Miao, Zhengke - Powiązania:
- https://bibliotekanauki.pl/articles/30148675.pdf
- Data publikacji:
- 2014-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
edge coloring
edge-chromatic critical graphs
independence number - Opis:
- In 1968, Vizing conjectured that for any edge chromatic critical graph $G = (V,E)$ with maximum degree $△$ and independence number $α(G)$, $α(G) ≤ \frac{|V|}{2}$. It is known that $α(G) < \frac{3∆−2}{5∆−2}|V|$. In this paper we improve this bound when $△≥4$. Our precise result depends on the number $n_2$ of 2-vertices in $G$, but in particular we prove that $α(G) ≤\frac{3∆−3}{5∆−3}|V|$ when $△≥5$ and $n_2≤2(△− 1)$.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2014, 34, 3; 577-584
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł