A bound for the chromatic number of (P2 ∪ P4,diamond)-free graphs

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 Mathematics, Algorithms & Applications 17(2025) 1−12]. This bound is tight for [Formula: see text], achieved by the complement of the famous 27-vertex Schl[Formula: see text]fli graph.