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 条
  • [11] The Game Coloring Number of Planar Graphs with a Specific Girth
    Keaitsuda Maneeruk Nakprasit
    Kittikorn Nakprasit
    Graphs and Combinatorics, 2018, 34 : 349 - 354
  • [12] The game coloring number of planar graphs with a given girth
    Sekiguchi, Yosuke
    DISCRETE MATHEMATICS, 2014, 330 : 11 - 16
  • [13] Faster algorithms for subgraph isomorphism of k-connected partial k-trees
    Dessmark, A
    Lingas, A
    Proskurowski, A
    ALGORITHMICA, 2000, 27 (3-4) : 337 - 347
  • [14] Algorithms for generalized vertex-rankings of partial k-trees
    Kashem, MA
    Zhou, X
    Nishizeki, T
    THEORETICAL COMPUTER SCIENCE, 2000, 240 (02) : 407 - 427
  • [15] Finding edge-disjoint paths in partial k-trees
    Zhou, X
    Tamura, S
    Nishizeki, T
    ALGORITHMICA, 2000, 26 (01) : 3 - 30
  • [16] Finding edge-disjoint paths in partial k-trees
    Zhou, XA
    Tamura, S
    Nishizeki, T
    ALGORITHMS AND COMPUTATION, 1996, 1178 : 203 - 212
  • [17] Sharp lower bounds of the least eigenvalue of planar graphs
    Hong, Y
    Shu, JL
    LINEAR ALGEBRA AND ITS APPLICATIONS, 1999, 296 (1-3) : 227 - 232
  • [18] A linear algorithm for finding [g, f]-colorings of partial k-trees
    Zhou, X
    Fuse, K
    Nishizeki, T
    ALGORITHMICA, 2000, 27 (3-4) : 227 - 243
  • [19] A linear algorithm for finding [g, f]-colorings of partial k-trees
    Zhou X.
    Fuse K.
    Nishizeki T.
    Algorithmica, 2000, 27 (3-4) : 227 - 243
  • [20] On the Complexity of the Maximum Common Subgraph Problem for Partial k-Trees of Bounded Degree
    Akutsu, Tatsuya
    Tamura, Takeyuki
    ALGORITHMS AND COMPUTATION, ISAAC 2012, 2012, 7676 : 146 - 155
123