A note on class one graphs with maximum degree six

DOI10.1016/J.DISC.2006.02.007MaRDI QIDQ2497484zbMATH OpenOpenAlexFDO

Authors Xuechao Li, Rong Luo, Jianbing Niu

Publication date 4 August 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.02.007

zbMATH Keywords

class oneedge chromatic numberembeddingEuler characteristicplanar

Mathematics Subject Classification ID

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

Review text

A simple graph \(G=(V, E)\) is called class one if its edge chromatic number \(\chi_e(G)\) equals its maximum vertex degree \(\Delta(G)\) and is called class two, otherwise. (By Vizing's theorem, \(\chi_e(G) = \Delta(G)+1\), in this case.) Vizing's planar graph conjecture states that every planar graph with \(\Delta=6\) or \(7\) is class one. While the case \(\Delta = 7\) has been settled, this paper refines the \(\Delta=6\) case, by identifying 3 families of class one graphs, namely: \(C_3\)-free graphs which are embeddable in a surface with Euler characteristic at least \(-3\), \(C_4\)-free graphs which are embeddable in a surface with Euler characteristic at least \(-3\), \(C_5\)-free graphs which are embeddable in a surface with Euler characteristic at least \(-1\).

Recommendations

• Some sufficient conditions for a planar graph of maximum degree six to be Class 1
• A sufficient condition for a plane graph with maximum degree 6 to be class 1
• A new sufficient condition for a planar graph of maximum degree six to be class 1
• On Gallai's conjecture for graphs with maximum degree 6
• scientific article; zbMATH DE number 1135746
• Planar graphs of maximum degree six without 7-cycles are class one
• A note on graphs of class I
• A class of perfect graphs containing \(P_{6}\)
• Classifying character degree graphs with six vertices
• On the domination number of graphs with minimum degree six

Cites work

• A note on graphs of class I
• Chromatic index critical graphs of order 9
• Chromatic-index-critical graphs of orders 11 and 12
• Edge coloring of graphs with small average degrees
• Every planar graph with maximum degree 7 is of class 1
• scientific article; zbMATH DE number 3273761 (Why is no real title available?)
• On small graphs critical with respect to edge colourings
• Planar graphs of maximum degree seven are Class I

Cited in

(10)

• Classifying character degree graphs with six vertices
• Edge coloring of graphs embedded in a surface of nonnegative characteristic
• Finding \(\Delta (\Sigma)\) for a surface \(\Sigma \) of characteristic \(-6\) and \(-7\)
• A sufficient condition for a planar graph to be class I
• Some sufficient conditions for a planar graph of maximum degree six to be Class 1
• Finding () for a surface of characteristic -4
• Class I graphs of nonnegative characteristic without special cycles
• scientific article; zbMATH DE number 11798 (Why is no real title available?)
• Every planar graph with maximum degree 7 is of class 1
• A sufficient condition for edge 6-colorable planar graphs with maximum degree 6

This page was built for publication: A note on class one graphs with maximum degree six

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