Edge coloring graphs with large minimum degree

DOI10.1002/jgt.22889zbMath1522.05136arXiv2105.05286OpenAlexW3163381588MaRDI QIDQ6094039

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

chromatic index1-factorizationoverfull 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)

Related Items

Further split graphs known to be class 1 and a characterization of subgraph-overfull split graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 1-factorizing regular graphs of high degree - an improved bound
• A constructive proof of Vizing's theorem
• Edge coloring regular graphs of high degree
• How to find overfull subgraphs in graphs with large maximum degree. II
• 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
• Efficient parallel algorithms for edge coloring problems
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• The NP-Completeness of Edge-Coloring
• On Edge Coloring Bipartite Graphs
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Independent sets and 2‐factors in edge‐chromatic‐critical graphs
• An Asymptotic Version of the Multigraph 1‐Factorization Conjecture
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• The Solution of a Timetabling Problem
• Some Theorems on Abstract Graphs
• Optimal path and cycle decompositions of dense quasirandom graphs