2025/12/09 by N. Rahimi, Doost Ali Mojdeh, Rahimi, N. +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Advanced Combinatorial Mathematics
paper · pdf · doi:10.48550/arxiv.2512.09186
In this paper, we establish that the class of \P6, (2,2)-broom\-free graphs contains a subclass Li, defined by certain cutset conditions, whose chromatic number admits a linear χ-bound. Building on recent results showing that broom-free graphs excluding Kd(t) as a subgraph admit a polynomial bound in~t on their chromatic number (A broom is obtained from a path with one end v by adding leaves adjacent to v), we extend this result to the hereditary class H of C4-free and p-flag-free graphs (where a p-flag is a triangle with an attached p-path). We show that if G ∈ H is B+(p+2, t-1)-free (for p ≥ 2 and t ≥ 3, that is, if it excludes a generalized broom with an additional leaf), and does not contain Kd(t) as a subgraph, then χ(G) is polynomially bounded in t. Furthermore, for the subclass of H excluding K3(t) as a subgraph, we prove that χ(G) is linearly χ-bounded in ω(G).