• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Yang, D. (Yang, D..) [1]

Indexed by:

Scopus

Abstract:

This paper investigates a competitive version of the coloring game on a finite graph G. An asymmetric variant of the (r, d)-relaxed coloring game is called the (r, d)-relaxed (a, b)-coloring game. In this game, two players, Alice and Bob, take turns coloring the vertices of a graph G, using colors from a set X, with | X | = r. On each turn Alice colors a vertices and Bob colors b vertices. A color α ∈ X is legal for an uncolored vertex u if by coloring u with color α, the subgraph induced by all the vertices colored with α has maximum degree at most d. Each player is required to color an uncolored vertex legally on each move. The game ends when there are no remaining uncolored vertices. Alice wins the game if all vertices of the graph are legally colored, Bob wins if at a certain stage there exists an uncolored vertex without a legal color. The d-relaxed (a, b)-game chromatic number of G, denoted (a, b)-χgd (G), is the least r for which Alice has a winning strategy in the (r, d)-relaxed (a, b)-coloring game. This paper extends the well-studied activation strategy of coloring games to relaxed asymmetric coloring games. The extended strategy is then applied to the (r, d)-relaxed (a, 1)-coloring games on planar graphs, partial k-trees and (s, t)-pseudo-partial k-trees. This paper shows that for planar graphs G, if a ≥ 2, then (a, 1)-χgd (G) ≤ 6 for all d ≥ 77. If H is a partial k-tree, 1 ≤ a < k, then (a, 1)-χgd (H) ≤ k + 1 for all d ≥ 2 k + frac(2 k - 1, a). If H is an (s, t)-pseudo-partial k-tree, a ≥ 1, let φ (s, t, k, a) = (1 + frac(1, a)) (k2 + s k + t k + s t + k + t + 1) + k + t, then (a, 1)-χgd (H) ≤ k + 1 for all d ≥ φ (s, t, k, a). For planar graphs G and a ≥ 1, (a, 1)-χgd (G) ≤ 3 for all d ≥ 71 + frac(61, a). These results extend the corresponding (r, d)-relaxed (1, 1)-coloring game results to more generalized asymmetric cases. © 2008 Elsevier B.V. All rights reserved.

Keyword:

Asymmetric coloring games; Partial k-trees; Planar graphs; Pseudo-partial k-trees; Relaxed chromatic number

Community:

  • [ 1 ] [Yang, D.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian 350002, China

Reprint 's Address:

  • [Yang, D.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian 350002, China

Show more details

Related Keywords:

Related Article:

Source :

Discrete Mathematics

ISSN: 0012-365X

Year: 2009

Issue: 10

Volume: 309

Page: 3323-3335

0 . 5 4 8

JCR@2009

0 . 7 0 0

JCR@2023

JCR Journal Grade:3

CAS Journal Grade:1

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 3

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:478/11140952
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1