The incidence game chromatic number of (a,d)-decomposable graphs

The incidence coloring game has been introduced in Andres (2009) [2] as a variation of the ordinary coloring game. The incidence game chromatic number ιg(G) of a graph G is the minimum number of colors for which Alice has a winning strategy when playing the incidence coloring game on G. In Charpenti...

Full description

Saved in:
Bibliographic Details
Published in:Journal of discrete algorithms (Amsterdam, Netherlands) Netherlands), 2015-03, Vol.31, p.14-25
Main Authors: Charpentier, C., Sopena, É.
Format: Article
Language:English
Subjects:
[formula omitted]-decomposable graphs
Arboricity
Computer Science
Discrete Mathematics
Incidence coloring
Incidence coloring game
Incidence game chromatic number
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The incidence coloring game has been introduced in Andres (2009) [2] as a variation of the ordinary coloring game. The incidence game chromatic number ιg(G) of a graph G is the minimum number of colors for which Alice has a winning strategy when playing the incidence coloring game on G. In Charpentier and Sopena (2013) [7], we proved that ιg(G)≤⌊3Δ(G)−a2⌋+8a−1 for every graph G with arboricity at most a. In this paper, we extend our previous result to (a,d)-decomposable graphs – that is graphs whose set of edges can be partitioned into two parts, one inducing a graph with arboricity at most a, the other inducing a graph with maximum degree at most d – and prove that ιg(G)≤⌊3Δ(G)−a2⌋+8a+3d−1 for every (a,d)-decomposable graph G.
ISSN:1570-8667
1570-8675
DOI:10.1016/j.jda.2014.10.001