M-Degrees of Quadrangle-Free Planar Graphs

被引：8

作者：

Borodin, Olleg V. ^{[1
]}

Kostochka, Allexandr V. ^{[1
,2
]}

Sheikh, Naeern N. ^{[2
]}

Yu, Gexin ^{[3
]}

机构：

[1] Sobolev Inst Math, Novosibirsk 630090, Russia

[2] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[3] Vanderbilt Univ, Dept Math, Nashville, TN 37240 USA

来源：

JOURNAL OF GRAPH THEORY | 2009年 / 60卷 / 01期

关键词：

planar graphs; decomposition; degree; game coloring; THEOREM;

D O I：

10.1002/jgt.20346

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The M-degree of an edge xy in a graph is the maximum of the degrees of x and y. The M-degree of a graph G is the minimum over M-degrees of its edges. In order to get upper bounds on the game chromatic number, He et al showed that every planar graph G without leaves and 4-cycles has M-degree at most 8 and gave an example of such a graph with M-degree 3. This yields upper bounds on the game chromatic number of C-4-free planar graphs. We determine the maximum possible M-degrees for planar, projective-planar and toroidal graphs without leaves and 4-cycles. In particular, for planar and projective-planar graphs this maximum is 7. (C) 2008 Wiley Periodicals Inc. J Graph Theory 60: 80-85, 2009

引用

页码：80 / 85

页数：6

共 5 条

[1]

Borodin OV, 1996, J GRAPH THEOR, V23, P233, DOI 10.1002/(SICI)1097-0118(199611)23:3<233::AID-JGT3>3.3.CO

[2]

2-I

[3] GENERALIZATION OF A THEOREM OF KOTZIG AND A PRESCRIBED COLORING OF THE EDGES OF PLANAR GRAPHS [J].