On the Independence Number of Edge Chromatic Critical Graphs
Shiyou Pang, Lianying Miao, Wenyao Song, Zhengke Miao (2014)
Discussiones Mathematicae Graph Theory
Similarity:
In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤ [...] . It is known that α (G) < [...] |V |. In this paper we improve this bound when △≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α (G) ≤ [...] |V | when △ ≥ 5 and n2 ≤ 2(△− 1)