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

DOI10.1002/JGT.22933zbMATH Open1522.05061arXiv2301.02140MaRDI QIDQ6074595FDOQ6074595

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)

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).

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

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

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)

Cites Work

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

Cited In (6)

• Title not available (Why is that?)
• On the average degree of critical graphs with maximum degree six
• Face-degree bounds for planar critical graphs
• On the density of \(C_7\)-critical graphs
• Subcubic edge-chromatic critical graphs have many edges
• Tuza's conjecture for graphs with maximum average degree less than 7

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)