Back to search

Georgia Institute of Technology

On probabilistic, planar, and descriptive graph coloring problems

Abstract

dc:description.abstract

We 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 × 11

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/76934

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Anderson, James. On probabilistic, planar, and descriptive graph coloring problems. Doctoral thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/76934