Three-coloring triangle-free graphs without long forbidden paths

Yidong Zhou, Jorik Jooken, Baoyuan Shan +2

A graph $G$ is $k$-vertex-critical if $\chi (G)=k$, but $\chi (G^{\prime })<k$ for every proper induced subgraph $G^{\prime }$ of $G$. For a family of graphs $\mathcal{F}$, $G$ is $\mathcal{F}$-free if no g…