Download this article
 Download this article For screen
For printing
Recent Issues

Volume 17, 1 issue

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editors’ Interests
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 Lundon, Jennifer Firkins Nordstrom, Cassandra Naymie, Erin Pitney, William Sehorn and Charlie Suer

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

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 of a particular subclass of outerplanar graphs, then χg(2)(H) 3.

competitive coloring, outerplanar graph, clique, relaxed coloring
Mathematical Subject Classification 2000
Primary: 05C15
Received: 27 August 2010
Revised: 10 February 2011
Accepted: 11 February 2011
Published: 17 January 2012

Communicated by Vadim Ponomarenko
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
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