The edge coloring game on trees with the number of colors greater than the game chromatic index

Wai Lam Fong () and Wai Hong Chan ()

Journal of Combinatorial Optimization, 2019, vol. 38, issue 2, No 8, 456-480

Abstract: Abstract Let $$X\in \{A,B\}$$ X ∈ { A , B } and $$Y\in \{A,B,-\}$$ Y ∈ { A , B , - } , where A, B and − denote (player) Alice, (player) Bob and none of the players, respectively. In the k-[X, Y]-edge-coloring game, Alice and Bob alternately choose a color from a given color set with k colors to color an uncolored edge of a graph G such that no adjacent edges receive the same color. Player X begins and Player Y has the right to skip any number of turns. Alice wins the game if all the edges of G are finally colored; otherwise, Bob wins. The [X, Y]-game chromatic index of an uncolored graph G, denoted by $$\chi '_{[X,Y]}(G)$$ χ [ X , Y ] ′ ( G ) , is the least k such that Alice has a winning strategy for the game. We prove that, for any [X, Y], Alice has a winning strategy for the k-[X, Y]-edge-coloring game on any tree T when $$k>\chi '_{[X,Y]}(T)$$ k > χ [ X , Y ] ′ ( T ) . Moreover, using some parts of the proofs of the above results, we show that there is a tree T satisfying $$\chi '_{[A,-]}(T)

Keywords: Game chromatic index; Game chromatic number; Graph coloring game; Tree; Line graph (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00395-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:2:d:10.1007_s10878-019-00395-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00395-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().