Planar graphs with cycles of length neither 4 nor 6 are (2,0,0)-colorable

被引：13

作者：

Wang, Yingqian ^{[1
]}

Xu, Jinghan ^{[1
]}

机构：

[1] Zhejiang Normal Univ, Coll Math Phys & Informat Engn, Jinhua 321004, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2013年 / 113卷 / 18期

关键词：

Combinatorial problems; Planar graph; Cycle; Improper coloring; COLORINGS; MAP;

D O I：

10.1016/j.ipl.2013.06.001

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let d(1),d(2), ... , d(k) be k non-negative integers. A graph G is (d(1), d(2), ... , d(k))-colorable, if the vertex set of G can be partitioned into subsets V-1, V-2, ... , V-k such that the graph G[V-i] induced by V-i has maximum degree at most d(i) for i = 1, 2, ... , k. In this paper, we show that planar graphs with cycles of length neither 4 nor 6 are (2, 0, 0)-colorable. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：659 / 663

页数：5

共 18 条

[1] EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING [J].

APPEL, K ;

HAKEN, W .

ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :429-490

[2] EVERY PLANAR MAP IS 4 COLORABLE .2. REDUCIBILITY [J].

APPEL, K ;

HAKEN, W ;

KOCH, J .

ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :491-567

[3] Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable [J].

Borodin, O. V. ;

Glebov, A. N. ;

Raspaud, A. .

DISCRETE MATHEMATICS, 2010, 310 (20) :2584-2594

[4]

Chang G.J., 2011, PREPRINT

[5] DEFECTIVE COLORINGS OF GRAPHS IN SURFACES - PARTITIONS INTO SUBGRAPHS OF BOUNDED VALENCY [J].

COWEN, LJ ;

COWEN, RH ;

WOODALL, DR .

JOURNAL OF GRAPH THEORY, 1986, 10 (02) :187-195

[6] A note on list improper coloring of plane graphs [J].

Dong, Wei ;

Xu, Baogang .

DISCRETE APPLIED MATHEMATICS, 2009, 157 (02) :433-436

[7]

Eaton N., 1999, Bull. Inst. Combin. Appl., V25, P79

[8]

GROTZSCH H., 1959, DREIFARBENSATZ D M N, V8, P109

[9]

Hill O., DISCRETE MA IN PRESS

[10]

Kang Y, PLANAR GRAPHS UNPUB

← 1 2 →