The average degree of edge chromatic critical graphs with maximum degree seven

DOI10.1002/JGT.22933MaRDI QIDQ6074595zbMATH OpenFDO

Authors Yan Cao, Rong Luo, Zhengke Miao, Yue Zhao

Publication date 12 October 2023

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

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

zbMATH Keywords

planar graphsedge coloringcritical graphsEuler formula

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: In this paper, by developing several new adjacency lemmas about a path on $4$ or $5$ vertices, we show that the average degree of 7-critical graphs is at least 6. It implies Vizing's planar graph conjecture for planar graphs with maximum degree $7$ and its extension to graphs embeddable in a surface with nonnegative Euler characteristic due to Sanders and Zhao (J. Combin. Theory Ser. B 83 (2001) 201-212 and J. Combin. Theory Ser. B 87 (2003) 254-263) and Zhang (Graphs and Combinatorics 16 (2000) 467-495).

Recommendations

• Average degrees of edge-chromatic critical graphs
• On the average degree of edge chromatic critical graphs
• Edge coloring of graphs with small average degrees
• On the size of critical graphs with small maximum degree
• The average degree of an edge‐chromatic critical graph II

Cites work

• scientific article; zbMATH DE number 3654142 (Why is no real title available?)
• scientific article; zbMATH DE number 3273761 (Why is no real title available?)
• An improvement to the Hilton-Zhao vertex-splitting conjecture
• Coloring edges of graphs embedded in a surface of characteristic zero.
• Every planar graph with maximum degree 7 is of class 1
• Finding \(\Delta(\Sigma )\) for a surface \(\Sigma\) of characteristic \(\chi(\Sigma) = -5\)
• Finding \(\Delta(\Sigma)\) for a surface \(\Sigma\) of characteristic \(-4\)
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• Graph edge coloring: a survey
• On critical graphs with chromatic index 4
• On the average degree of edge chromatic critical graphs
• On the average degree of edge chromatic critical graphs. II.
• On the size of edge-chromatic critical graphs
• Planar graphs of maximum degree seven are Class I
• SOME UNSOLVED PROBLEMS IN GRAPH THEORY
• The average degree of an edge‐chromatic critical graph II
• The size of edge chromatic critical graphs with maximum degree 6

Cited in

(6)

• Subcubic edge-chromatic critical graphs have many edges
• Tuza's conjecture for graphs with maximum average degree less than 7
• On the average degree of critical graphs with maximum degree six
• On the density of \(C_7\)-critical graphs
• Face-degree bounds for planar critical graphs
• scientific article; zbMATH DE number 5613296 (Why is no real title available?)

This page was built for publication: The average degree of edge chromatic critical graphs with maximum degree seven

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