Lower bounds for the game colouring number of partial k-trees and planar graphs

被引：24

作者：

Wu, Jiaojiao ^{[1
]}

Zhu, Xuding ^{[2
,3
]}

机构：

[1] Acad Sinica, Inst Math, Taipei 115, Taiwan

[2] Natl Sun Yat Sen Univ, Dept Appl Math, Kaohsiung, Taiwan

[3] Natl Ctr Theoret Sci, Kaohsiung, Taiwan

来源：

DISCRETE MATHEMATICS | 2008年 / 308卷 / 12期

关键词：

game colouring number; game chromatic number; partial k-tree; planar graph;

D O I：

10.1016/j.disc.2007.05.023

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

This paper discusses the game colouring number of partial k-trees and planar graphs. Let col(g)(PTk) and col(g)(P) denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this paper, we prove that col(g)(PTk) = 3k + 2 and col(g)(P) >= 11. We also prove that the game colouring number col(g)(G) of a graph is a monotone parameter, i.e., if H is a subgraph of G, then col(g)(H) <= col(g)(G). (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：2637 / 2642

页数：6

共 22 条

[1] The game coloring number of pseudo partial k-trees
Zhu, XD
DISCRETE MATHEMATICS, 2000, 215 (1-3) : 245 - 262
[2] Partial k-trees with maximum chromatic number
Chlebíková, J
DISCRETE MATHEMATICS, 2002, 259 (1-3) : 269 - 276
[3] Parallel recognition algorithms for chordal_planar graphs and planar k-trees
Panda, BS
Das, SK
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2005, 65 (08) : 922 - 926
[4] Transversals of longest cycles in partial k-trees and chordal graphs
Gutierrez, Juan
JOURNAL OF GRAPH THEORY, 2021, 98 (04) : 589 - 603
[5] NOTE ON THE GAME COLOURING NUMBER OF POWERS OF GRAPHS
Andres, Stephan Dominique
Theuser, Andrea
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (01) : 31 - 42
[6] Algorithms for multicolorings of partial k-trees
Ito, T
Nishizeki, T
Zhou, X
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2003, E86D (02) : 191 - 200
[7] The game coloring number of planar graphs
Zhu, XD
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 75 (02) : 245 - 258
[8] The strong game colouring number of directed graphs
Chan, Wai Hong
Shiu, Wai Chee
Sun, Pak Kiu
Zhu, Xuding
DISCRETE MATHEMATICS, 2013, 313 (10) : 1070 - 1077
[9] Generalized vertex-colorings of partial k-trees
Zhou, X
Kanari, Y
Nishizeki, T
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2000, E83A (04) : 671 - 678
[10] The Game Coloring Number of Planar Graphs with a Specific Girth
Nakprasit, Keaitsuda Maneeruk
Nakprasit, Kittikorn
GRAPHS AND COMBINATORICS, 2018, 34 (02) : 349 - 354

← 1 2 3 →