Sparse color-critical graphs and rainbow matchings in edge-colored graphs

critical graphs;coloring sparse graphs;improper graph coloring;relaxed graph coloring

Yancey, Matthew

关键词: critical graphs;    coloring sparse graphs;    improper graph coloring;    relaxed graph coloring;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/44365/Matthew_Yancey.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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, includinga 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, anda 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$.