#### Vol. 4, No. 2, 2011

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
Clique-relaxed graph coloring

### Charles Dunn, Jennifer Firkins Nordstrom, Cassandra Naymie, Erin Pitney, William Sehorn and Charlie Suer

Vol. 4 (2011), No. 2, 127–138
##### Abstract

We define a generalization of the chromatic number of a graph $G$ called the $k$-clique-relaxed chromatic number, denoted ${\chi }^{\left(k\right)}\left(G\right)$. We prove bounds on ${\chi }^{\left(k\right)}\left(G\right)$ for all graphs $G$, including corollaries for outerplanar and planar graphs. We also define the $k$-clique-relaxed game chromatic number, ${\chi }_{g}^{\left(k\right)}\left(G\right)$, of a graph $G$. We prove ${\chi }_{g}^{\left(2\right)}\left(G\right)\le 4$ for all outerplanar graphs $G$, and give an example of an outerplanar graph $H$ with ${\chi }_{g}^{\left(2\right)}\left(H\right)\ge 3$. Finally, we prove that if $H$ is a member of a particular subclass of outerplanar graphs, then ${\chi }_{g}^{\left(2\right)}\left(H\right)\le 3$.

##### Keywords
competitive coloring, outerplanar graph, clique, relaxed coloring
Primary: 05C15