Chromatic bounds of some (P5, banner)-free graphs
C. U. Angeliya, Sheshayya Choudum, Mayamma Joseph
Source record
Source: Crossref
Published: Mar 4, 2026
DOI: 10.1142/s1793557126500257
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]. A [Formula: see text] is a path on five vertices, a banner (paw) is the graph obtained by joining a new vertex to a single vertex of [Formula: see text] ([Formula: see text]) and a hammer is obtained by subdividing the pendant edge of a paw exactly once. Recently, [Formula: see text]-free graphs have received wide attention. In 2019, Karthick, Maffray and Pastor, gave a structural characterisation of [Formula: see text]-free graphs, which when combined with a result by Bourneuf and Thomassé [Bounded twin-width graphs are polynomially [Formula: see text]-bounded, Adv. Comb. (2025)] implies that for a [Formula: see text]-free graph [Formula: see text], [Formula: see text]. Geißer [Colourings of [Formula: see text]-Free Graphs, PhD Thesis, Technische Universit at Bergakademie Freiberg (2022)] showed that the [Formula: see text]-binding function of the class of [Formula: see text]-free graphs is bounded by the [Formula: see text]-binding function of [Formula: see text]-free graphs. By a result of Kim [The Ramsey number [Formula: see text] has order of magnitude [Formula: see text], Random Structures and Algorithms 7(3) (1995) 173–207], the chromatic number [Formula: see text] of a [Formula: see text]-free graph [Formula: see text] has order of magnitude [Formula: see text]. Recently, Song and Xu [Divisibility and coloring of some [Formula: see text]-free graphs, Discrete Appl. Math. 348 (2024) 144–151] proved that every ([Formula: see text], [Formula: see text], banner, hammer)-free graph [Formula: see text] is [Formula: see text]-colorable. This motivates us to study the subclasses of ([Formula: see text], banner)-free graphs. We prove that for any ([Formula: see text], banner, [Formula: see text])-free graph [Formula: see text] where [Formula: see text], [Formula: see text] for [Formula: see text]. Moreover, the bound is tight for [Formula: see text].
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.