The overfull conjecture on graphs of odd order and large minimum degree

DOI10.1002/JGT.23077arXiv2205.08564OpenAlexW4391822283MaRDI QIDQ6399418FDOQ6399418

Authors: Songling Shan 

Publication date: 17 May 2022

Abstract: Let $G$ be a simple graph with maximum degree $Delta(G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>Delta(G)lfloorfrac12|V(H)|floor$. Chetwynd and Hilton in 1986 conjectured that a graph $G$ with $Delta(G)>frac13|V(G)|$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph. Let $0<varepsilon<1$ and $G$ be a large graph on $n$ vertices with minimum degree at least $frac12(1+varepsilon)n$. It was shown that the conjecture holds for $G$ if $n$ is even. In this paper, the same result is proved if $n$ is odd. As far as we know, this is the first result on the conjecture for graphs of odd order and with a minimum degree constraint.

Full work available at URL: https://doi.org/10.1002/jgt.23077

Recommendations

• Edge coloring graphs with large minimum degree
• Overfull conjecture for graphs with high minimum degree
• scientific article; zbMATH DE number 1998290
• The chromatic index of graphs with large even order \(n\) and minimum degree at least \(2n/3\)
• Chromatic index of dense quasirandom graphs

Mathematics Subject Classification ID

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

Cited In (1)

• Maximum odd induced subgraph of a graph concerning its chromatic number

This page was built for publication: The overfull conjecture on graphs of odd order and large minimum degree

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