A simple graph G is called $$\varDelta$$ Δ - critical if $$\chi '(G) =\varDelta (G) +1$$ χ ′ ( G ) = Δ ( G ) + 1 and $$\chi… Click to show full abstract
A simple graph G is called $$\varDelta$$ Δ - critical if $$\chi '(G) =\varDelta (G) +1$$ χ ′ ( G ) = Δ ( G ) + 1 and $$\chi '(H) \le \varDelta (G)$$ χ ′ ( H ) ≤ Δ ( G ) for every proper subgraph H of G , where $$\varDelta (G)$$ Δ ( G ) and $$\chi '(G)$$ χ ′ ( G ) are the maximum degree and the chromatic index of G , respectively. Vizing in 1965 conjectured that any $$\varDelta$$ Δ -critical graph contains a 2-factor, which is commonly referred to as Vizing’s 2-factor conjecture ; In 1968, he proposed a weaker conjecture that the independence number of any $$\varDelta$$ Δ -critical graph with order n is at most n /2, which is commonly referred to as Vizing’s independence number conjecture . Based on a construction of $$\varDelta$$ Δ -critical graphs which is called Meredith extension first given by Meredith, we show that if $$\alpha (G')\le (\frac{1}{2}+f(\varDelta ))|V(G')|$$ α ( G ′ ) ≤ ( 1 2 + f ( Δ ) ) | V ( G ′ ) | for every $$\varDelta$$ Δ -critical graph $$G'$$ G ′ with $$\delta (G')=\varDelta -1,$$ δ ( G ′ ) = Δ - 1 , then $$\alpha (G)<\big (\frac{1}{2}+f(\varDelta )(2\varDelta -5)\big )|V(G)|$$ α ( G ) < ( 1 2 + f ( Δ ) ( 2 Δ - 5 ) ) | V ( G ) | for every $$\varDelta$$ Δ -critical graph G with maximum degree $$\varDelta ,$$ Δ , where f is a nonnegative function of $$\varDelta .$$ Δ . We also prove that any $$\varDelta$$ Δ -critical graph contains a 2-factor if and only if its Meredith extension contains a 2-factor.
               
Click one of the above tabs to view related content.