Upper bounds on the maximum degree of class two graphs on surfaces

被引：0

作者：

Horacek, Katie ^{[1
]}

Luo, Rong ^{[2
]}

Miao, Zhengke ^{[3
]}

Zhao, Yue ^{[4
]}

机构：

[1] Frostburg State Univ, Dept Math, Frostburg, MD 21532 USA

[2] West Virginia Univ, Dept Math, Morgantown, WV 26506 USA

[3] Jiangsu Normal Univ, Sch Math & Stat, Xuzhou 221116, Jiangsu, Peoples R China

[4] Univ Cent Florida, Dept Math, Orlando, FL 32816 USA

来源：

DISCRETE MATHEMATICS | 2020年 / 343卷 / 03期

关键词：

Edge colorings; Class one; Class two; Critical graphs; Surfaces; CHROMATIC INDEX; EDGE COLORINGS; SIGMA;

D O I：

10.1016/j.disc.2019.111738

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For each surface Sigma, we define Delta(Sigma)=max{Delta(G)vertical bar G is a class two graph with maximum degree Delta(G) that can be embedded on Sigma}. Hence Vizing's Planar Graph Conjecture can be restated as Delta(Sigma) = 5 if Sigma is a sphere. For a surface Sigma with Euler characteristic chi, it is known Delta(Sigma) >= H(chi) - 1 where H(chi) is the Heawood number of the surface and if the Euler characteristic chi is an element of {-7, -6, ..., -1, 0}, Delta(Sigma) is already known. In this paper, we study critical graphs on general surfaces and show that if G is a critical graph embeddable on a surface Sigma with Euler characteristic chi <= -8, then Delta(G) <= H(chi) (or H(chi) + 1) for some special families of graphs, namely if the minimum degree is at most 11 or if Delta is very large etc. As applications, we show that Delta(Sigma) <= H(chi) if chi is an element of (-22, -21, .., -8) \ {-19, -16 and Delta(Sigma) <= H(chi) + 1 if chi is an element of (-53, ..., -23} boolean OR (-19, -16}. Combining this with jungerman (1974), it follows that if chi = -12 and Sigma is orientable, then, Delta(Sigma) = H(chi). (C) 2019 Elsevier B.V. All rights reserved.

引用

页数：17