M-degrees of quadrangle-free planar graphs
M-degrees of quadrangle-free planar graphs
复制标题
DOI：
10.1002/jgt.v60:1
复制
发表时间：
2009
影响因子：
0.9
通讯作者：
O. Borodin;A. Kostochka;N. Sheikh;Gexin Yu
中科院分区：
文献类型：
--
作者：
O. Borodin;A. Kostochka;N. Sheikh;Gexin Yu
图的边xy的M度是x和y的度的最大值，图G的M度是图G的边的M度上的最小值。为了得到对策色数的上界，他等人证明了无叶4圈的平面图G的M度至多为8，并给出了一个M度为3的图的例子。这给出了无C4平面图的对策色数的上界。我们确定了平面图、射影平面图和环形图的最大可能的M度。特别是，对于平面和投影平面图形，这一最大值为7。#2008 Wiley期刊，Inc.图形理论60：80-85,2009
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 C4-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. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 80–85, 2009