On the Independence Number of Edge Chromatic Critical Graphs

Discussiones Mathematicae Graph Theory

Miao Zhengke¹  Miao Lianying¹  Pang Shiyou²  Song Wenyao² 

[1] Department of Mathematics, Jiangsu Normal University, Xuzhou, Jiangsu, 221116, P.R.China;School of Science, China University of Mining and Technology Xuzhou, Jiangsu, 221008, P.R.China;

关键词: edge coloring;    edge-chromatic critical graphs;    independence number;   

DOI  :  10.7151/dmgt.1753

来源: DOAJ

【 摘 要 】

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)

【 授权许可】

Unknown