Files in this item

FilesDescriptionFormat

application/pdf

application/pdf3023179.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Coloring Problems on Graphs and Hypergraphs
Author(s):Ramamurthi, Radhika
Doctoral Committee Chair(s):West, Douglas B.
Department / Program:Mathematics
Discipline:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Mathematics
Abstract: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.
Issue Date:2001
Type:Text
Language:English
Description:103 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2001.
URI:http://hdl.handle.net/2142/86787
Other Identifier(s):(MiAaPQ)AAI3023179
Date Available in IDEALS:2015-09-28
Date Deposited:2001


This item appears in the following Collection(s)

Item Statistics