Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Mathematics
The Game Chromatic Number Of Trees And Forests, Charles Dunn, Victor Larsen, Troy Retter, Kira Lindke, Dustin Toci
The Game Chromatic Number Of Trees And Forests, Charles Dunn, Victor Larsen, Troy Retter, Kira Lindke, Dustin Toci
Faculty Publications
While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests with game chromatic number 3 and 4. In doing so, we present a minimal example of a forest with game chromatic number 4, criteria for determining in polynomial time the game chromatic number of a forest without vertices of degree 3, and an example of a forest with maximum degree …
The Relaxed Edge-Coloring Game And K-Degenerate Graphs, Charles Dunn, David Morawski, Jennifer Firkins Nordstrom
The Relaxed Edge-Coloring Game And K-Degenerate Graphs, Charles Dunn, David Morawski, Jennifer Firkins Nordstrom
Faculty Publications
The (r, d)-relaxed edge-coloring game is a two-player game using r colors played on the edge set of a graph G. We consider this game on forests and more generally, on k-degenerate graphs. If F is a forest with ∆(F) = ∆, then the first player, Alice, has a winning strategy for this game with r = ∆ − j and d ≥ 2j + 2 for 0 ≤ j ≤ ∆ − 1. This both improves and generalizes the result for trees in [10]. More broadly, we generalize the main result in [10] …