Vizing's 2-factor conjecture involving toughness and maximum degree conditions

MaRDI QIDQ2415079zbMATH OpenFDO

Authors Jinko Kanno, Songling Shan

Publication date 20 May 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.02241, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i2p17

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

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

Abstract: Let $G$ be a simple graph, 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$. We say $G$ is $Delta$-critical if $ch{i}^{\prime }(G)=Delta+1$ and $ch{i}^{\prime }(H)<ch{i}^{\prime }(G)$ for every proper subgraph $H$ of $G$. In 1968, Vizing conjectured that if $G$ is a $Delta$-critical graph, then $G$ has a 2-factor. Let $G$ be an $n$-vertex $Delta$-critical graph. It was proved that if $Delta(G)gen/2$, then $G$ has a 2-factor; and that if $Delta(G)ge2n/3+12$, then $G$ has a hamiltonian cycle, and thus a 2-factor. It is well known that every 2-tough graph with at least three vertices has a 2-factor. We investigate the existence of a 2-factor in a $Delta$-critical graph under "moderate" given toughness and maximum degree conditions. In particular, we show that if $G$ is an $n$-vertex $Delta$-critical graph with toughness at least 3/2 and with maximum degree at least $n/3$, then $G$ has a 2-factor. In addition, we develop new techniques in proving the existence of 2-factors in graphs.

Review text

Summary: Let \(G\) be a simple graph, and let \(\Delta(G)\) and \(\chi'(G)\) denote the maximum degree and chromatic index of \(G\), respectively. Vizing proved that \(\chi'(G)=\Delta(G)\) or \(\chi'(G)=\Delta(G)+1\). We say \(G\) is \(\Delta\)-critical if \(\chi'(G)=\Delta(G)+1\) and \(\chi'(H)<\chi'(G)\) for every proper subgraph \(H\) of \(G\). In 1968, Vizing conjectured that if \(G\) is a \(\Delta\)-critical graph, then \(G\) has a 2-factor. Let \(G\) be an \(n\)-vertex \(\Delta\)-critical graph. It was proved that if \(\Delta(G)\ge n/2\), then \(G\) has a 2-factor; and that if \(\Delta(G)\ge 2n/3+13\), then \(G\) has a hamiltonian cycle, and thus a 2-factor. It is well known that every 2-tough graph with at least three vertices has a 2-factor. We investigate the existence of a 2-factor in a \(\Delta\)-critical graph under ``moderate given toughness and maximum degree conditions. In particular, we show that if \(G\) is an \(n\)-vertex \(\Delta\)-critical graph with toughness at least 3/2 and with maximum degree at least \(n/3\), then \(G\) has a 2-factor. We also construct a family of graphs that have order \(n\), maximum degree \(n-1\), toughness at least \(3/2\), but have no 2-factor. This implies that the \(\Delta\)-criticality in the result is needed. In addition, we develop new techniques in proving the existence of 2-factors in graphs.

Recommendations

• Vizing's 2-factor conjecture involving large maximum degree
• 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
• Edge‐chromatic critical graphs and the existence of 1‐factors
• (2,k)-factor-critical graphs and toughness

Cites work

• A new upper bound for the independence number of edge chromatic critical graphs
• A note on Vizing's independence number conjecture of edge chromatic critical graphs
• A Short Proof of the Factor Theorem for Finite Graphs
• A sufficient condition for edge chromatic critical graphs to be Hamiltonian -- an approach to Vizing's 2-factor conjecture
• Average degrees of edge-chromatic critical graphs
• Bounds for the Independence Number of Critical Graphs
• Hamiltonian cycles in critical graphs with large maximum degree
• scientific article; zbMATH DE number 3266380 (Why is no real title available?)
• scientific article; zbMATH DE number 3273761 (Why is no real title available?)
• scientific article; zbMATH DE number 3284071 (Why is no real title available?)
• Independent sets and 2‐factors in edge‐chromatic‐critical graphs
• The existence of a 2-factor in \(K_{1,n}\)-free graphs with large connectivity and large edge-connectivity
• The existence of a 2-factor in a graph satisfying the local Chvátal-Erdős condition
• The independence number of an edge-chromatic critical graph
• The NP-Completeness of Edge-Coloring
• Toughness and the existence ofk-factors
• Vizing's 2-factor conjecture involving large maximum degree

Cited in

(9)

• Graph edge coloring: a survey
• Reducing Vizing's 2-factor conjecture to Meredith extension of critical graphs
• Vizing's 2-factor conjecture involving large maximum degree
• A sufficient condition for edge chromatic critical graphs to be Hamiltonian -- an approach to Vizing's 2-factor conjecture
• Forbidden subgraphs and 2‐factors in 3/2‐tough graphs
• On the chromatic edge stability index of graphs
• Existence of 2-factors in tough graphs without forbidden subgraphs
• Strong binding numbers and factors
• Toughness and the existence of 2-factors

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

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