Georgia Institute of Technology
On probabilistic, planar, and descriptive graph coloring problems
Abstract
dc:description.abstractWe investigate graph coloring problems from the perspective of three different types of graphs: graphs with forbidden bipartite subgraphs; planar graphs; and Borel graphs that are line graphs. We start with studying graph with forbidden bipartite subgraphs. We say a graph is $F$-free if it contains no subgraph (not necessarily induced) isomorphic to graph $F$. It follows from recent work by Davies, Kang, Pirot, and Sereni that if $G$ is Kt,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$. We further extend our result to the correspondence coloring setting. Next we study defective coloring of planar graphs. For $d \in \mathbb{N}$, a coloring of a graph is \textit{$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.
Degree
thesis:*- Level thesis:degree_level
- Doctoral
- Department dc:contributor.department
- Mathematics
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Anderson, James
- Advisors dc:contributor.advisor
-
- Bernshteyn, Anton
- McCarty, Rose
- Committee members dc:contributor.committeemember
-
- Kaul, Hemanshu
- Kelly, Tom
- Yu, Xingxing
Subjects
dc:subject × 11Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/76934