IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Polynomial χ-binding functions for graph classes

  • Oct. 15, 2021
  • 2:30 p.m.

Abstract

A graph class is called polynomially $\chi$-bounded if there is a function $f$ such that $\chi(G) \leq f(\omega(G))$ for every graph $G$ in this class, where $\chi(G)$ and $\omega(G)$ denote the chromatic number and clique number of $G$ respectively. A t-broom is a graph obtained from $K _ {1,t+1}$ by subdividing an edge once. A fork is a graph obtained from $K _ {1,4}$ by subdividing two edges. We show two conjectures: (1) we show that for graphs $G$ without induced $t$-brooms, $\chi(G) = o(\omega(G)^{t+1})$, answering a question of Schiermeyer and Randerath. For $t=2$, we strengthen the bound on $\chi(G)$ to $7.5\omega(G)^2$, confirming a conjecture of Sivaraman. (2) We show that any {triangle, fork}-free graph $G$ satisfies $\chi(G)\leq \omega(G)+1$, confirming a conjecture of Randerath.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC