Coloring Problems on Graphs and Hypergraphs

An r-edge-coloring of Kn is (r, m)-splittable if V (Kn) can then be r-colored to avoid totally monochromatic m-cliques (introduced by Erdo&huml;s and Gyarfas. We interpret such colorings using a two-round game against an adversary; this relates splittable colorings to classical Ramsey numbers. Let fr(m) be the least n such that some r-edge-coloring of K n is not (r, m)-splittable. Combinatorial designs yield fr(m) ≤ O(r2m2). Extending ideas of Erdo&huml;s and Gyarfas yields f r(m) ≥ min{O(rm 2), O(r2m)}. Similar bounds hold for a generalization to hypergraphs.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Ramamurthi, Radhika

Contributors dc:contributor

• West, Douglas B.

• Mathematics

Language dc:language

eng

Identifier

(MiAaPQ)AAI3023179

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/86787