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

Title

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

Creator

Angeliya, C.U.; Choudum, Sheshayya; Joseph, Mayamma

Description

Let ?(G) and ?(G), respectively, denote the chromatic number and clique number of a graph G. A P5 is a path on five vertices, a banner (paw) is the graph obtained by joining a new vertex to a single vertex of C4 (C3) and a hammer is obtained by subdividing the pendant edge of a paw exactly once. Recently, (P5,banner)-free graphs have received wide attention. In 2019, Karthick, Maffray and Pastor, gave a structural characterisation of (P5,banner)-free graphs, which when combined with a result by Bourneuf and Thomass[Bounded twin-width graphs are polynomially ?-bounded, Adv. Comb. (2025)] implies that for a (P5,banner)-free graph G, ?(G) ? ?(G)5. Geir [Colourings of P5-Free Graphs, PhD Thesis, Technische Universit at Bergakademie Freiberg (2022)] showed that the ?-binding function of the class of (P5,banner)-free graphs is bounded by the ?-binding function of 3K1-free graphs. By a result of Kim [The Ramsey number R(3,t) has order of magnitude t2/log t, Random Structures and Algorithms 7(3) (1995) 173207], the chromatic number ?(G) of a 3K1-free graph G has order of magnitude ?(?(G)2/log ?(G)). Recently, Song and Xu [Divisibility and coloring of some P5-free graphs, Discrete Appl. Math. 348 (2024) 144151] proved that every (P5, C5, banner, hammer)-free graph G is ?(G)3/2-colorable. This motivates us to study the subclasses of (P5, banner)-free graphs. We prove that for any (P5, banner, F ? K1)-free graph G where F ?{C4,K4 ? e,K3 ? K1,paw}, ?(G) ? ?(G)2/2 for ?(G) ? 3. Moreover, the bound is tight for ?(G) = 3. 2026 World Scientific Publishing Company.

Source

Asian-European Journal of Mathematics;Issue;;Article No.;2650025;

Date

01-01-2026

Publisher

World Scientific

Subject

(P₅, banner)-free graphs; chromatic number; clique number; Graph classes

Coverage

Angeliya C.U., Department of Mathematics, CHRIST (Deemed to be University), Karnataka, Bangalore, 560029, India; Choudum S., Department of Mathematics, CHRIST (Deemed to be University), Karnataka, Bangalore, 560029, India; Joseph M., Department of Mathematics, CHRIST (Deemed to be University), Karnataka, Bangalore, 560029, India

Rights

Restricted Access; Hardcopy may be available in the library

Relation

ISSN: 17935571;

Format

online

Language

English

Type

Article

Identifier

https://doi.org/10.1142/S1793557126500257

https://www.scopus.com/pages/publications/105032237008?origin=resultslist