## Files in this item

FilesDescriptionFormat

application/pdf

Matthew_Yancey.pdf (894kB)
(no description provided)PDF

application/pdf

Setup.pdf (27kB)
(no description provided)PDF

application/pdf

sasha1b.pdf (5kB)
(no description provided)PDF

application/pdf

(no description provided)PDF

application/pdf

LStoGraph.pdf (13kB)
(no description provided)PDF

application/pdf

HypergraphConstruction3.pdf (4kB)
(no description provided)PDF

application/pdf

HypergraphConstruction2.pdf (4kB)
(no description provided)PDF

application/pdf

HypergraphConstruction1.pdf (2kB)
(no description provided)PDF

application/pdf

GallaiBoundsChart.pdf (39kB)
(no description provided)PDF

application/pdf

G4G5InitialGraph.pdf (12kB)
(no description provided)PDF

application/pdf

fk_sharp_examples.pdf (3kB)
(no description provided)PDF

application/pdf

fig-precol2-best.pdf (13kB)
(no description provided)PDF

application/pdf

fig-precol2.pdf (26kB)
(no description provided)PDF

application/pdf

fig-thomas-wals.pdf (3kB)
(no description provided)PDF

application/pdf

fig-4face.pdf (27kB)
(no description provided)PDF

application/pdf

fig-3prism.pdf (2kB)
(no description provided)PDF

application/pdf

f_k_examples.pdf (7kB)
(no description provided)PDF

application/pdf

DiracBoundsChart.pdf (27kB)
(no description provided)PDF

application/pdf

ConfigurationB_BW.pdf (26kB)
(no description provided)PDF

application/pdf

ConfigurationA_BW.pdf (24kB)
(no description provided)PDF

application/pdf

4crit_examples.pdf (7kB)
(no description provided)PDF

application/pdf

3crit_odd.pdf (1kB)
(no description provided)PDF

application/pdf

3crit_hypergraph.pdf (2kB)
(no description provided)PDF

application/pdf

1,1-G3'.pdf (9kB)
(no description provided)PDF

application/pdf

1,1-G3.pdf (8kB)
(no description provided)PDF

## Description

 Title: Sparse color-critical graphs and rainbow matchings in edge-colored graphs Author(s): Yancey, Matthew Director of Research: Kostochka, Alexandr V. Doctoral Committee Chair(s): Balogh, Jozsef Doctoral Committee Member(s): Kostochka, Alexandr V.; West, Douglas B.; Lidicky, Bernard Department / Program: Mathematics Discipline: Mathematics Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): critical graphs coloring sparse graphs improper graph coloring relaxed graph coloring Abstract: This thesis focuses on extremal problems about coloring graphs and on finding rainbow matchings in edge-colored graphs. A graph $G$ is $k$-{\em critical} if $G$ is not $(k-1)$-colorable, but every proper subgraph of $G$ is $(k-1)$-colorable. Let $f_k(n)$ denote the minimum number of edges in an $n$-vertex $k$-critical graph. We present a lower bound, $f_k(n) \geq F(k,n)$, that is sharp whenever $n=1\,({\rm mod }\, k-1)$. It establishes the asymptotics of $f_k(n)$ for every fixed $k$, and confirms a conjecture by Gallai. We also present several applications of the proof, including a polynomial-time algorithm for $(k-1)$-coloring a graph $G$ that satisfies $|E(G[W])| < F(k, |W|)$ for all $W \subseteq V(G)$, several results about $3$-coloring planar graphs, and a lower bound on the minimum number of edges in an $n$-vertex $k$-critical hypergraph. We also present a lower bound on the number of edges in graphs that cannot be $1$-defectively $2$-colored. The bound solves an open problem in vertex Ramsey theory. A \textit{rainbow subgraph} of an edge-colored graph is a subgraph whose edges have distinct colors. The \textit{color degree} of a vertex $v$ is the number of different colors on edges incident to $v$. We show that if $G$ is a $n$-vertex graph with minimum color degree $k$, then $G$ contains a rainbow matching of size at least $k/2$ always and size at least $k$ if $n\geq 4.25k^2$. Issue Date: 2013-05-24 URI: http://hdl.handle.net/2142/44365 Rights Information: Copyright 2013 Matthew Yancey Date Available in IDEALS: 2013-05-24 Date Deposited: 2013-05
﻿