Chromatic bounds of some (P5, banner)-free graphs
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].
Authors
- S.A. Choudum
- Mathew Joseph (ORCID: https://orcid.org/0000-0001-5819-247X)
- C. U. Angeliya
Institutions
- Christ University (IN)
Publication Details
- Journal
- Asian-European Journal of Mathematics
- Published
- 2026-02-13
- DOI
- https://doi.org/10.1142/s1793557126500257
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00