Physical Sciences and Mathematics Commons^™

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⁽²⁾(G)≤ 4 for all outerplanar graphs G, and give an example of an outerplanar graph H with χ_g⁽²⁾(H) ≥ 3. Finally, we prove that if H is a member …