MATH Seminar
| Title: An epsilon improvement to the asymptotic density of k-critical graphs |
|---|
| Defense: Dissertation |
| Speaker: Victor Larsen of Emory University |
| Contact: Victor Larsen, vlarsen@emory.edu |
| Date: 2015-04-08 at 4:30PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: Given a graph $G$ the \emph{chromatic number}, denoted $\chi(G)$, is smallest number of colors necessary to color $V(G)$ such that no adjacent vertices receive the same color. A graph $G$ is $k$-critical if $\chi(G)=k$ but every proper subgraph has chromatic number less than $k$. As $k$-critical graphs can be viewed as minimal examples of graphs with chromatic number $k$, it is natural to ask how small such a graph can be. Let $f_k(n)$ denote the minimum number of edges in a $k$-critical graph on $n$ vertices. The Ore construction, used to build larger $k$-critical graphs, implies that \[f_k(n+k-1)\leq f_k(n)+(k-1)\left(\frac{k}{2}-\frac{1}{k-1}\right).\] A recent paper by Kostochka and Yancey provides a lower bound for $f_k(n)$ which implies that the asymptotic density $\phi_k:=\lim_{n\to\infty}f_k(n)/n = \frac{k}{2}-\frac{1}{k-1}$. In this work, we use the method of discharging to prove a lower bound on the number of edges which includes structural information about the graph. This lower bound shows that the asymptotic density of a $k$-critical graph can be increased by $\epsilon>0$ by restricting to $(K_{k-2})$-free $k$-critical graphs.\\ \\ We also prove that the graphs constructible from the Ore construction and $K_k$, called \emph{$k$-Ore} graphs, are precisely the graphs which attain Kostochka and Yancey's bound. Moreover, we also provide results regarding subgraphs which must exist in $k$-Ore graphs. For the discharging argument, carried out in two stages, we also prove results regarding the density of nearly-bipartite subgraphs in $k$-critical graphs. |
See All Seminars