Files in this item

FilesDescriptionFormat

application/pdf

application/pdfMatthew_Yancey.pdf (894kB)
(no description provided)PDF

application/pdf

application/pdfSetup.pdf (27kB)
(no description provided)PDF

application/pdf

application/pdfsasha1b.pdf (5kB)
(no description provided)PDF

application/pdf

application/pdfRadioTowers.pdf (14kB)
(no description provided)PDF

application/pdf

application/pdfLStoGraph.pdf (13kB)
(no description provided)PDF

application/pdf

application/pdfHypergraphConstruction3.pdf (4kB)
(no description provided)PDF

application/pdf

application/pdfHypergraphConstruction2.pdf (4kB)
(no description provided)PDF

application/pdf

application/pdfHypergraphConstruction1.pdf (2kB)
(no description provided)PDF

application/pdf

application/pdfGallaiBoundsChart.pdf (39kB)
(no description provided)PDF

application/pdf

application/pdfG4G5InitialGraph.pdf (12kB)
(no description provided)PDF

application/pdf

application/pdffk_sharp_examples.pdf (3kB)
(no description provided)PDF

application/pdf

application/pdffig-precol2-best.pdf (13kB)
(no description provided)PDF

application/pdf

application/pdffig-precol2.pdf (26kB)
(no description provided)PDF

application/pdf

application/pdffig-thomas-wals.pdf (3kB)
(no description provided)PDF

application/pdf

application/pdffig-4face.pdf (27kB)
(no description provided)PDF

application/pdf

application/pdffig-3prism.pdf (2kB)
(no description provided)PDF

application/pdf

application/pdff_k_examples.pdf (7kB)
(no description provided)PDF

application/pdf

application/pdfDiracBoundsChart.pdf (27kB)
(no description provided)PDF

application/pdf

application/pdfConfigurationB_BW.pdf (26kB)
(no description provided)PDF

application/pdf

application/pdfConfigurationA_BW.pdf (24kB)
(no description provided)PDF

application/pdf

application/pdf4crit_examples.pdf (7kB)
(no description provided)PDF

application/pdf

application/pdf3crit_odd.pdf (1kB)
(no description provided)PDF

application/pdf

application/pdf3crit_hypergraph.pdf (2kB)
(no description provided)PDF

application/pdf

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

application/pdf

application/pdf1,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


This item appears in the following Collection(s)

Item Statistics