Premium
Vizing's 2‐Factor Conjecture Involving Large Maximum Degree
Author(s) -
Chen Guantao,
Shan Songling
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22135
Subject(s) - combinatorics , mathematics , conjecture , simple graph , vertex (graph theory) , graph , hamiltonian path , edge coloring , degree (music) , discrete mathematics , graph power , line graph , physics , acoustics
Let G be an n ‐vertex simple graph, and let Δ ( G ) andχ ′ ( G )denote the maximum degree and chromatic index of G , respectively. Vizing proved thatχ ′ ( G ) = Δ ( G )or Δ ( G ) + 1 . Define G to be Δ‐critical ifχ ′ ( G ) = Δ + 1 andχ ′ ( H ) < χ ′ ( G )for every proper subgraph H of G . In 1965, Vizing conjectured that if G is an n ‐vertex Δ‐critical graph, then G has a 2‐factor. Luo and Zhao showed if G is an n ‐vertex Δ‐critical graph with Δ ( G ) ≥ 6 n / 7 , then G has a hamiltonian cycle, and so G has a 2‐factor. In this article, we show that if G is an n ‐vertex Δ‐critical graph with Δ ( G ) ≥ n / 2 , then G has a 2‐factor.