The game chromatic index of trees of maximum degree 4 with at most three degree-four vertices in a row

2019/04/02 by Wai Lam Fong, Fong, Wai Lam, Wai Hong Chan +1
Computer Science · Mathematics · #05C05 #05C15 #05C57 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1904.01496

openalex publication_date 2019/04/02 · openalex created_date 2019/04/11 · openalex updated_date 2026/07/28

Abstract

Fong et al. (The game chromatic index of some trees with maximum degree four and adjacent degree-four vertices, J. Comb Optim 36 (2018) 1-12) proved that the game chromatic index of any tree T of maximum degree 4 whose degree-four vertices induce a forest of paths of length l less than 2 is at most 5. In this paper, we show that the bound 5 is also valid for l≤ 2. This partially solves the problem of characterization of the trees whose game chromatic index exceeds the maximum degree by at most 1, which was proposed by Cai and Zhu (Game chromatic index of k-degenerate graphs, J. Graph Theory 36 (2001) 144-155).

Related

• Edge colouring Game on Trees with maximum degree Δ=4
• The game chromatic number of trees and forests
• A new upper bound on the game chromatic index of graphs
• List edge-colouring and total colouring in graphs of low treewidth
• The game chromatic number of dense random graphs