Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic \(\epsilon \in \{-1, -2, -3\}\)
type: Item
instance of: scholarly article
title: Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic \(\epsilon \in \{-1, -2, -3\}\)
zbMATH Open document ID: 1148.05029
author: Rong Luo
author: Yue Zhao
published in: Journal of Combinatorial Theory. Series B
publication date: 2008-07-24T00:00:00Z
review text: A graph \(G\) of maximum degree \(\Delta\) is class one if it is edge \(\Delta\)-colorable, and of class two otherwise (in which case, by \textit{V. G. Vizing's} theorem [Diskret. Analiz, Novosibirsk 5, 9--17 (1965; Zbl 0171.44902)]), it is edge \((\Delta+ 1)\)-colorable). For a surface \(S\), \(\Delta(S)\) is the largest \(\Delta(G)\) among all class two graphs \(G\) imbeddable on \(S\). Vizing's planar graph conjecture is that \(\Delta(S)= 5\), if \(S\) is the sphere (which has characteristic 2). The authors show that \(\Delta(S)= 7\) if \(S\) has characteristic \(-1\), and that \(\Delta(S)= 8\), if \(S\) has characteristic either \(-2\) or \(-3\).
reviewed by: Arthur T. White
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5303723
zbMATH Keywords: edge colorings
zbMATH Keywords: class one
zbMATH Keywords: class two
zbMATH Keywords: critical graphs
zbMATH Keywords: surfaces
MaRDI profile type: Publication
full work available at URL: j.jctb.2007.11.002
OpenAlex ID: W2156102353
cites work: Every planar map is four colorable. I: Discharging
cites work: Every Planar Map is Four Colorable
cites work: On small graphs critical with respect to edge colourings
cites work: Chromatic-index-critical graphs of orders 13 and 14
cites work: 3- and 4-critical graphs of small even order
cites work: Chromatic-index-critical graphs of orders 11 and 12
cites work: Chromatic index critical graphs of order 9
cites work: Edge colorings of graphs embeddable in a surface of low genus
cites work: The chromatic class and the location of a graph on a closed surface
cites work: SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
cites work: Planar graphs of maximum degree seven are Class I
cites work: Coloring edges of graphs embedded in a surface of characteristic zero.
cites work: Q5558480
cites work: SOME UNSOLVED PROBLEMS IN GRAPH THEORY
cites work: Edge colorings of embedded graphs
cites work: Every planar graph with maximum degree 7 is of class 1
DOI: 10.1016/J.JCTB.2007.11.002
description: scientific article; zbMATH DE number 5303723