Vol. 4, No. 2, 2011

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

Volume 10
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180

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
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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 χ(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.

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 Dunn
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