Bounding the chromatic number of squares of K4-minor-free graphs

被引：4

作者：

Civan, Yusuf ^{[1
]}

Deniz, Zakir ^{[2
]}

Yetim, Mehmet Akif ^{[1
]}

机构：

[1] Suleyman Demirel Univ, Dept Math, TR-32260 Isparta, Turkey

[2] Duzce Univ, Dept Math, TR-81620 Duzce, Turkey

来源：

DISCRETE MATHEMATICS | 2019年 / 342卷 / 07期

关键词：

K-4-minor-free graph; Square graph; Chromatic number; PLANAR GRAPHS;

D O I：

10.1016/j.disc.2019.03.011

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a K-4-minor-free graph with Delta(G) >= 3. We prove that if G contains no subgraph isomorphic to K-2(,r) for some r >= 1. then chi(G(2)) <= Delta(G) + r. (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：1894 / 1903

页数：10

共 9 条

[1] Colorings of plane graphs: A survey
Borodin, O. V.
[J]. DISCRETE MATHEMATICS, 2013, 313 (04) : 517 - 539
[2] 2-distance (Δ+2)-coloring of planar graphs with girth six and Δ ≥ 18
Borodin, O. V.
Ivanova, A. O.
[J]. DISCRETE MATHEMATICS, 2009, 309 (23-24) : 6496 - 6502
[3] Dirac G.A., 1952, J LONDON MATH SOC, V27, P85
[4] Hartke S.G., 2016, PREPRINT
[5] A Brooks-type bound for squares of K4-minor-free graphs
Kostochka, Alexandr V.
Ozkahya, Lale
Woodall, Douglas R.
[J]. DISCRETE MATHEMATICS, 2009, 309 (23-24) : 6572 - 6584
[6] Coloring the square of a K4-minor free graph
Lih, KW
Wang, WF
Zhu, XD
[J]. DISCRETE MATHEMATICS, 2003, 269 (1-3) : 303 - 309
[7] The square of a planar cubic graph is 7-colorable
Thomassen, Carsten
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2018, 128 : 192 - 218
[8] Labelling planar graphs without 4-cycles with a condition on distance two
Wang, Weifan
Cai, Leizhen
[J]. DISCRETE APPLIED MATHEMATICS, 2008, 156 (12) : 2241 - 2249
[9] Wegner G., 1977, TECHNICAL REPORT

← 1 →