Vizing's 2-factor conjecture involving large maximum degree

DOI10.1002/JGT.22135MaRDI QIDQ4596325zbMATH OpenOpenAlexWikidataFDO

Authors Guantao Chen, Songling Shan

Publication date 1 December 2017

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.6299

zbMATH Keywords

critical graphsedge chromatic indexTutte's 2-factor theorem

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Abstract: Let $G$ be a connected simple graph of order $n$ and let $Delta(G)$ and $ch{i}^{\prime }(G)$ denote the maximum degree and chromatic index of $G$, respectively. Vizing proved that $ch{i}^{\prime }(G)=Delta(G)$ or $Delta(G)+1$. Following this result, $G$ is called $Delta$-critical if $ch{i}^{\prime }(G)=Delta(G)+1$ and $ch{i}^{\prime }(G-e)=Delta(G)$ for every $einE(G)$. In 1968, Vizing conjectured that if $G$ is an $n$-vertex $Delta$-critical graph, then the independence number $alpha(G)len/2$. Furthermore, he conjectured that, in fact, $G$ has a 2-factor. Luo and Zhao showed that if $G$ is an $n$-vertex $Delta$-critical graph with $Delta(G)gen/2$, then $alpha(G)len/2$. More recently, they showed that if $G$ is an $n$-vertex $Delta$-critical graph with $Delta(G)ge6n/7$, then $G$ has a hamiltonian cycle, and so $G$ has a 2-factor. In this paper, we show that if $G$ is an $n$-vertex $Delta$-critical graph with $Delta(G)gen/2$, then $G$ has a 2-factor.

Recommendations

• Vizing's 2-factor conjecture involving toughness and maximum degree conditions
• A sufficient condition for edge chromatic critical graphs to be Hamiltonian -- an approach to Vizing's 2-factor conjecture
• Reducing Vizing's 2-factor conjecture to Meredith extension of critical graphs
• A note on Vizing's independence number conjecture of edge chromatic critical graphs
• Independent sets and 2‐factors in edge‐chromatic‐critical graphs

Cited in

(7)

• Graph edge coloring: a survey
• Reducing Vizing's 2-factor conjecture to Meredith extension of critical graphs
• Vizing's 2-factor conjecture involving toughness and maximum degree conditions
• Even factors in edge-chromatic-critical graphs with a small number of divalent vertices
• Hamiltonian cycles in critical graphs with large maximum degree
• Independent sets and 2‐factors in edge‐chromatic‐critical graphs
• A sufficient condition for edge chromatic critical graphs to be Hamiltonian -- an approach to Vizing's 2-factor conjecture

This page was built for publication: Vizing's 2-factor conjecture involving large maximum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4596325)