Answers are grounded in this paper and cite their sources.
Authors demonstrate chromatic bounds in banner-free graphs, suggesting new implications for graph theory.
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 5 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é (2023) implies that for a [Formula: see text]-free graph [Formula: see text], [Formula: see text]. Geißer in his thesis (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 (1995), 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 (2024) 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].
No takes yet. Share an insight, caveat, or question.
Angeliya et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: