Optimal chromatic bounds to two open problems on P 5 -free graphs
C. U. Angeliya, Sheshayya Choudum, Mayamma Joseph
Source record
Source: Crossref
Published: Sep 10, 2026
DOI: 10.1142/s1793557126501147
Open original source ↗Source 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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.