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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Chromatic bounds of some (P5, banner)-free graphs

S.A. Choudum, Mathew Joseph, C. U. Angeliya
Asian-European Journal of Mathematics
Advanced Graph Theory Research
article

Chromatic bounds of some (P5, banner)-free graphs

S.A. Choudum, Mathew Joseph, C. U. Angeliya
article en

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].

Asian-European Journal of Mathematics
Christ University (IN)
Openalex Percentile: Top 55%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Chromatic bounds of some (P5, banner)-free graphs — S.A. Choudum, Mathew Joseph, et al. · Asian-European Journal of Mathematics (2026) | TGRS Research Map | TGRS