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