|
|||||
 |
|
|
|
|
|
|
|
Clique-relaxed
graph coloring
Charles Lundon, 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 called the -clique-relaxed chromatic number, denoted . We prove bounds on for all graphs , including corollaries for outerplanar and planar graphs. We also define the -clique-relaxed game chromatic number, , of a graph . We prove for all outerplanar graphs , and give an example of an outerplanar graph with . Finally, we prove that if is a member of a particular subclass of outerplanar graphs, then . |
Keywords
competitive coloring, outerplanar graph, clique, relaxed
coloring
|
Mathematical Subject Classification 2000
Primary: 05C15
|
Milestones
Received: 27 August 2010
Revised: 10 February 2011
Accepted: 11 February 2011
Published: 17 January 2012
Communicated by Vadim Ponomarenko
|
Authors |
| Charles Lundon | |
| Department of Mathematics Linfield College 900 SE Baker Street, Unit A468 McMinnville, OR 97128 United States |
|
| Jennifer Firkins Nordstrom | |
| Department of Mathematics Linfield College 900 SE Baker Street, Unit A468 McMinnville, OR 97128 United States |
|
| Cassandra Naymie | |
| University of Waterloo 200 University Avenue West Waterloo, Ontario N2L 3G1 Canada |
|
| Erin Pitney | |
| Meadow Park Middle School Beaverton School District 16550 SW Merlo Road Beaverton, OR 97006 United States |
|
| William Sehorn | |
| Whitworth University 300 W. Hawthorne Road Spokane, WA 99251 United States |
|
| Charlie Suer | |
| Department of Mathematics University of Louisville Louisville, KY 40292 United States |
|
| © 2011 MSP (Mathematical Sciences Publishers). |
