On the independence number of edge chromatic critical graphs

Szczegóły
Opis

Tytuł:: On the independence number of edge chromatic critical graphs
Autorzy:: Pang, Shiyou
Miao, Lianying
Song, Wenyao
Miao, Zhengke
Data publikacji:: 2014-08-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: edge coloring
edge-chromatic critical graphs
independence number
Język:: angielski
Prawa:: CC BY-NC-ND: Creative Commons Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 4.0
Źródło:: Discussiones Mathematicae Graph Theory; 2014, 34, 3; 577-584
2083-5892
Dostawca treści:: Biblioteka Nauki
: Artykuł

Przejdź do źródła

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)$.

Informacja