TY - JOUR

T1 - Chromatic capacity and graph operations

AU - Huizenga, Jack

N1 - Funding Information:
I would like to thank Josh Greene, Matt Elder, Melanie Wood, and Joseph Gallian for numerous helpful discussions. This research was conducted in Duluth, Minnesota at Joseph Gallian's REU program under grants from the National Science Foundation (DMS-0137611) and the National Security Agency (H-98230-04-1-0050).

PY - 2008/6/6

Y1 - 2008/6/6

N2 - The chromatic capacityχcap (G) of a graph G is the largest k for which there exists a k-coloring of the edges of G such that, for every coloring of the vertices of G with the same colors, some edge is colored the same as both its vertices. We prove that there is an unbounded function f : N → N such that χcap (G) ≥ f (χ (G)) for almost every graph G, where χ denotes the chromatic number. We show that for any positive integers n and k with k ≤ n / 2 there exists a graph G with χ (G) = n and χcap (G) = n - k, extending a result of Greene. We obtain bounds on χcap (Knr) that are tight as r → ∞, where Knr is the complete n-partite graph with r vertices in each part. Finally, for any positive integers p and q we construct a graph G with χcap (G) + 1 = χ (G) = p that contains no odd cycles of length less than q.

AB - The chromatic capacityχcap (G) of a graph G is the largest k for which there exists a k-coloring of the edges of G such that, for every coloring of the vertices of G with the same colors, some edge is colored the same as both its vertices. We prove that there is an unbounded function f : N → N such that χcap (G) ≥ f (χ (G)) for almost every graph G, where χ denotes the chromatic number. We show that for any positive integers n and k with k ≤ n / 2 there exists a graph G with χ (G) = n and χcap (G) = n - k, extending a result of Greene. We obtain bounds on χcap (Knr) that are tight as r → ∞, where Knr is the complete n-partite graph with r vertices in each part. Finally, for any positive integers p and q we construct a graph G with χcap (G) + 1 = χ (G) = p that contains no odd cycles of length less than q.

UR - http://www.scopus.com/inward/record.url?scp=40649094793&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=40649094793&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2006.10.021

DO - 10.1016/j.disc.2006.10.021

M3 - Article

AN - SCOPUS:40649094793

SN - 0012-365X

VL - 308

SP - 2134

EP - 2148

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 11

ER -