A bound for the chromatic number of (P2 ∪ P4,diamond)-free graphs
Li Zhang, Xia Hong
Source record
Source: Crossref
Published: Sep 7, 2026
DOI: 10.1142/s1793830926500795
Open original source ↗Source abstract
A hereditary class [Formula: see text] of graphs is [Formula: see text]-bounded if there is a [Formula: see text]-binding function, say [Formula: see text], such that [Formula: see text], for every [Formula: see text], where [Formula: see text] denotes the chromatic (clique) number of [Formula: see text]. A [Formula: see text] is the graph obtained by taking the disjoint union of a two-vertex path [Formula: see text] and a four-vertex path [Formula: see text], and a diamond is a graph obtained from [Formula: see text] by removing an edge. In this paper, we show that every [Formula: see text]-free graph [Formula: see text] with [Formula: see text] satisfies [Formula: see text]. This improves the result in [R. Chen and X. Zhang, Coloring of some [Formula: see text]-free graphs, Discrete Math. Algorithms Appl. 17 (2025) 1–12]. This bound is tight for [Formula: see text], achieved by the complement of the famous 27-vertex Schläfli graph.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.