Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 4 of 4
Full-Text Articles in Physical Sciences and Mathematics
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] …
Complete Multipartite Graphs And The Relaxed Coloring Game, Charles Dunn
Complete Multipartite Graphs And The Relaxed Coloring Game, Charles Dunn
Faculty Publications
Let k be a positive integer, d be a nonnegative integer, and G be a finite graph. Two players, Alice and Bob, play a game on G by coloring the uncolored vertices with colors from a set X of k colors. At all times, the subgraph induced by a color class must have maximum degree at most d. Alice wins the game if all vertices are eventually colored; otherwise, Bob wins. The least k such that Alice has a winning strategy is called the d-relaxed game chromatic number of G, denoted χ gd (G). …
Clique-Relaxed Graph Coloring, Charles Dunn, Jennifer Firkins Nordstrom, Cassandra Naymie, Erin Pitney, William Sehorn, Charlie Suer
Clique-Relaxed Graph Coloring, Charles Dunn, Jennifer Firkins Nordstrom, Cassandra Naymie, Erin Pitney, William Sehorn, Charlie Suer
Faculty Publications
We define a generalization of the chromatic number of a graph G called the k-clique-relaxed chromatic number, denoted χ(k)(G). We prove bounds on χ(k)(G) for all graphs G, including corollaries for outerplanar and planar graphs. We also define the k-clique-relaxed game chromatic number, χg(k)(G), of a graph G. We prove χg(2)(G)≤ 4 for all outerplanar graphs G, and give an example of an outerplanar graph H with χg(2)(H) ≥ 3. Finally, we prove that if H is a member …
The Relaxed Game Chromatic Index Of K-Degenerate Graphs, Charles Dunn
The Relaxed Game Chromatic Index Of K-Degenerate Graphs, Charles Dunn
Faculty Publications
The (r, d)-relaxed coloring game is a two-player game played on the vertex set of a graph G. We consider a natural analogue to this game on the edge set of G called the (r, d)-relaxed edge-coloring game. We consider this game on trees and more generally, on k-degenerate graphs. We show that if G is k-degenerate with ∆(G) = ∆, then the first player, Alice, has a winning strategy for this game with r = ∆+k−1 and d≥2k2 + 4k.