Chromatic index of dense quasirandom graphs

DOI10.1016/J.JCTB.2022.08.001zbMATH Open1497.05100arXiv2104.06253OpenAlexW4292771434MaRDI QIDQ2171027FDOQ2171027

Authors: Songling Shan 

Publication date: 23 September 2022

Published in: Journal of Combinatorial Theory. Series B (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$ on $n$ vertices with $Delta(G)>n/3$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph. Glock, K"{u}hn and Osthus in 2016 showed that the conjecture is true for dense quasirandom graphs with even order, and they conjectured that the same should hold for such graphs with odd order. In this paper, we show that the conjecture of Glock, K"{u}hn and Osthus is affirmative.

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

Recommendations

• Edge coloring graphs with large minimum degree
• The overfullness of graphs with small minimum degree and large maximum degree
• Overfull conjecture for graphs with high minimum degree
• The chromatic index of graphs with large even order \(n\) and minimum degree at least \(2n/3\)
• Two conjectures on edge-colouring

zbMATH Keywords

chromatic indexquasirandom graphoverfull graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The NP-Completeness of Edge-Coloring
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Title not available (Why is that?)
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Title not available (Why is that?)
• 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
• The Solution of a Timetabling Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An asymptotic version of the multigraph 1-factorization conjecture
• Overfull conjecture for graphs with high minimum degree

Cited In (4)

• The overfull conjecture on graphs of odd order and large minimum degree
• Overfull conjecture for graphs with high minimum degree
• The chromatic index of graphs with large even order \(n\) and minimum degree at least \(2n/3\)
• Edge coloring graphs with large minimum degree

This page was built for publication: Chromatic index of dense quasirandom graphs

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