Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic \(\epsilon \in \{-1, -2, -3\}\) (Q933675): Difference between revisions

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