Chromatic index of dense quasirandom graphs

DOI10.1016/J.JCTB.2022.08.001MaRDI QIDQ2171027zbMATH OpenOpenAlexFDO

Authors Songling Shan

Publication date 23 September 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

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)

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.

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

Cites work

• 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 852056 (Why is no real title available?)
• scientific article; zbMATH DE number 3266380 (Why is no real title available?)
• scientific article; zbMATH DE number 3273761 (Why is no real title available?)
• A constructive proof of Vizing's theorem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An asymptotic version of the multigraph 1-factorization conjecture
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• Independent sets and 2‐factors in edge‐chromatic‐critical 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
• The NP-Completeness of Edge-Coloring
• The Solution of a Timetabling Problem
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

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)