Edge coloring graphs with large minimum degree

DOI10.1002/JGT.22889zbMATH Open1522.05136arXiv2105.05286OpenAlexW3163381588MaRDI QIDQ6094039FDOQ6094039

Michael J. Plantholt, Songling Shan

Publication date: 9 October 2023

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

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.

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

zbMATH Keywords

1-factorizationchromatic indexoverfull conjectureoverfull graph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The NP-Completeness of Edge-Coloring
• Some Theorems on Abstract Graphs
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Efficient parallel algorithms for edge coloring problems
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On Edge Coloring Bipartite Graphs
• A constructive proof of Vizing's theorem
• Independent sets and 2‐factors in edge‐chromatic‐critical graphs
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• 1-factorizing regular graphs of high degree - an improved bound
• The Solution of a Timetabling Problem
• The chromatic index of graphs with large even order \(n\) and minimum degree at least \(2n/3\)
• Edge coloring regular graphs of high degree
• How to find overfull subgraphs in graphs with large maximum degree. II
• An Asymptotic Version of the Multigraph 1‐Factorization Conjecture
• Optimal path and cycle decompositions of dense quasirandom graphs
• Overfull conjecture for graphs with high minimum degree

Cited In (5)

• Further split graphs known to be class 1 and a characterization of subgraph-overfull split graphs
• Edge-coloring critical graphs with high degree
• The overfull conjecture on split-comparability and split-interval graphs
• Optimal edge coloring of large graphs
• Minimum number of palettes in edge colorings

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)