Optimal chromatic bounds to two open problems on P 5 -free graphs

Abstract

Let [Formula: see text] and [Formula: see text] respectively denote the chromatic number and clique number of a graph [Formula: see text]. In this paper, we present our contributions to two open problems on the coloring of [Formula: see text]-free graphs. A question posed by Gyárfás (1987) asks for the smallest [Formula: see text]-binding function for the class of [Formula: see text]-free graphs. We show that if [Formula: see text] is a [Formula: see text]-free graph, then [Formula: see text]. Thus, partially answering the question of Gyárfás for a subclass of [Formula: see text]-free graphs. Geißer (2022) and Huang et al. (2024) have independently conjectured that if [Formula: see text] is a [Formula: see text]-free graph, then [Formula: see text]. We establish that if [Formula: see text] is a [Formula: see text]-free graph, then [Formula: see text]. Thus, affirming this conjecture for a subclass of [Formula: see text]-free graphs. In addition, we prove that every [Formula: see text]-free graph [Formula: see text] is [Formula: see text]-colorable. Moreover, we construct extremal graphs showing that all these [Formula: see text]-binding functions are optimal.