On the Independence Number of Edge Chromatic Critical Graphs

Abstract

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)

Keywords

• edge coloring
• edge-chromatic critical graphs
• independence number