Georgia Institute of Technology College of Sciences

Graph coloring is a fundamental problem in graph theory in which the goal is to properly color a graph with the minimum number of colors in terms of some parameters (such as maximum degree). We explore this problem from the perspective of three different types of graphs: graphs with forbidden bipartite subgraphs; planar graphs; and Borel graphs that are line graphs. Each can be seen as graphs with a forbidden list of subgraphs; despite this similarity, the techniques used to study each are as varied as the results themselves.

We start with studying $F$-free graphs. We say a graph is $F$-free if it contains no subgraph isomorphic to $F$ (not necessarily induced). A conjecture of Alon, Krivelevich, and Sudakov states that, for any graph $F$, there is a constant $c_F > 0$ such that if $G$ is an $F$-free graph of maximum degree $\Delta$, then $\chi(G) \leq c_F \Delta / \log\Delta$. Alon, Krivelevich, and Sudakov verified this conjecture for a class of graphs $F$ that includes all bipartite graphs. Moreover, it follows from recent work by Davies, Kang, Pirot, and Sereni that %this conjecture holds for $F$ bipartite; moreover, if $G$ is $K_{t,t}$-free, then $\chi(G) \leq (t + o(1)) \Delta / \log\Delta$ as $\Delta \to \infty$. We improve this bound to $(1+o(1)) \Delta/\log \Delta$, making the constant factor independent of $t$. This matches the best known bound for several other class of graphs $F$, such as triangles, fans, and cycles, and lowering this bound further for nontrivial graphs is considered extremely challenging. We further extend our result to the correspondence coloring setting (also known as DP-coloring), introduced by Dvo\v{r}\'ak and Postle.

Next we study defective coloring of planar graphs. Defective coloring (also  known as relaxed or improper coloring) is a generalization of proper coloring defined as follows: for $d \in \mathbb{N}$, a coloring of a graph is $d$-defective if every vertex is colored the same as at most $d$ of its neighbors. We investigate defective coloring of planar graphs in the context of correspondence coloring. First we show there exist planar graphs that are not $3$-defective $3$-correspondable, strengthening a recent result of Cho, Choi, Kim, Park, Shan, and Zhu. Then we construct a planar graph that is $1$-defective $3$-correspondable but not $4$-correspondable, thereby extending a recent result of Ma, Xu, and Zhu from list coloring to correspondence coloring. Finally we show all outerplanar graphs are $3$-defective 2-correspondence colorable, with $3$ defects being best possible.

Finally, we study Borel graphs. We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the 9 finite graphs from the classical result of Beineke together with a 10th infinite graph associated to the equivalence relation $\mathbb{E}_0$ on the Cantor space. As a corollary, we prove a partial converse to the Feldman--Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers.

This includes work coauthored with Anton Bernshteyn and Abhishek Dhawan.