Two graph classes with bounded chromatic number

A class of graphs is said to be $\chi$-bounded with binding function $f$ if for every such graph $G$, it satisfies \chi(G) \leq f(ω(G), and polynomially $\chi$-bounded if $f$ is a polynomial. It was conjectured that chair-free graphs are perfectly divisible, and hence admit a quadratic $\chi$-binding function. In addition to confirming that chair-free graphs admit a quadratic $\chi$-binding function, we will extend the result by demonstrating that $t$-broom free graphs are polynomially $\chi$-bounded for any $t$ with binding function f(ω) = O(ω^t+1). A class of graphs is said to satisfy the Vizing bound if it admits the $\chi$-binding function f(ω) = ω + 1. It was conjectured that (fork, K₃)-free graphs would be 3-colorable, where fork is the graph obtained from K_{1, 4} by subdividing two edges. This would also imply that (paw, fork)-free graphs satisfy the Vizing bound. We will prove this conjecture through a series of lemmas that constrain the structure of any minimal counterexample.

Level thesis:degree_level

Doctoral

Department dc:contributor.department

Mathematics

Grantor dc:publisher

Georgia Institute of Technology

Year dc:date.issued

2023

Author dc:creator

• Schroeder, Joshua

Advisor dc:contributor.advisor

• Yu, Xingxing

Committee members dc:contributor.committeemember

• Bernshteyn, Anton
• Kelly, Tom
• Wang, Zhiyu
• Lu, Linyuan

• Graph theory
• graph coloring
• chromatic number
• chi-boundedness
• chi-binding functions

Language dc:language.iso

en_US

Handle dc:identifier.uri

https://hdl.handle.net/1853/72694

OAI identifier oai:identifier

oai:repository.gatech.edu:1853/72694