Edge coloring graphs with large minimum degree

DOI10.1002/JGT.22889MaRDI QIDQ6094039zbMATH OpenOpenAlexFDO

Authors Michael J. Plantholt, Songling Shan

Publication date 9 October 2023

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

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

zbMATH Keywords

1-factorizationchromatic indexoverfull conjectureoverfull graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: Let $G$ be a simple graph with maximum degree $Delta(G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>Delta(G)lfloor|V(H)|/2floor$. Chetwynd and Hilton in 1985 conjectured that a graph $G$ with $Delta(G)>|V(G)|/3$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph. The 1-factorization conjecture is a special case of this overfull conjecture, which states that for even $n$, every regular $n$-vertex graph with degree at least about $n/2$ has a 1-factorization and was confirmed for large graphs in 2014. Supporting the overfull conjecture as well as generalizing the 1-factorization conjecture in an asymptotic way, in this paper, we show that for any given $0<varepsilon<1$, there exists a positive integer $n_0$ such that the following statement holds: if $G$ is a graph on $2nge{n}_0$ vertices with minimum degree at least $(1+varepsilon)n$, then $G$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph.

Recommendations

• The chromatic index of graphs with large even order \(n\) and minimum degree at least \(2n/3\)
• Overfull conjecture for graphs with high minimum degree
• The overfullness of graphs with small minimum degree and large maximum degree
• Recent progress on edge-colouring graphs
• Chromatic index of dense quasirandom graphs

Cites work

• 1-factorizing regular graphs of high degree - an improved bound
• A constructive proof of Vizing's theorem
• An asymptotic version of the multigraph 1-factorization conjecture
• Edge coloring regular graphs of high degree
• Efficient parallel algorithms for edge coloring problems
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• Graph theory with applications
• How to find overfull subgraphs in graphs with large maximum degree. II
• scientific article; zbMATH DE number 4132188 (Why is no real title available?)
• scientific article; zbMATH DE number 3654142 (Why is no real title available?)
• scientific article; zbMATH DE number 3273761 (Why is no real title available?)
• Independent sets and 2‐factors in edge‐chromatic‐critical graphs
• On Edge Coloring Bipartite Graphs
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Overfull conjecture for graphs with high minimum degree
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Some Theorems on Abstract Graphs
• The chromatic index of graphs with large even order \(n\) and minimum degree at least \(2n/3\)
• The NP-Completeness of Edge-Coloring
• The Solution of a Timetabling Problem

Cited in

(21)

• Recent progress on edge-colouring graphs
• Two conjectures on edge-colouring
• How to find overfull subgraphs in graphs with large maximum degree
• Edge coloring regular graphs of high degree
• How to find overfull subgraphs in graphs with large maximum degree. II
• Edge-coloring critical graphs with high degree
• Minimum number of palettes in edge colorings
• The chromatic index of graphs with large even order \(n\) and minimum degree at least \(2n/3\)
• Chromatic index of dense quasirandom graphs
• Overfull conjecture for graphs with high minimum degree
• scientific article; zbMATH DE number 19203 (Why is no real title available?)
• Optimal edge coloring of large graphs
• The Hilton-Zhao conjecture is true for graphs with maximum degree 4
• The overfullness of graphs with small minimum degree and large maximum degree
• Chromatic index, treewidth and maximum degree
• The overfull conjecture on split-comparability and split-interval graphs
• On the inclusion chromatic index of a graph
• Further split graphs known to be class 1 and a characterization of subgraph-overfull split graphs
• The overfull conjecture on graphs of odd order and large minimum degree
• On the multigraph overfull conjecture
• Towards the overfull conjecture

This page was built for publication: Edge coloring graphs with large minimum degree

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