We use Pₜ and Cₜ to denote a path and a cycle on t vertices, respectively. A { bull} is a graph consisting of a triangle with two disjoint pendant edges, a { hammer} is a graph obtained by identifying an endvertex of a P₃ with a vertex of a triangle. A class F is χ-bounded if there is a function f such that χ(G)≤ f(ω(G)) for all induced subgraphs G of a graph in F. A class C of graphs is { Pollyanna} (resp. { linear-Pollyanna}) if C∩ F is polynomially (resp. linear-polynomially) χ-bounded for every χ-bounded class F of graphs. Chudnovsky { et al} {CCDO2023} showed that both the classes of bull-free graphs and hammer-free graphs are Pollyannas. Let G be a connected graph with no clique cutsets and no universal cliques. In this paper, we show that G is (C₄, hammer)-free if and only if it has girth at least 5, and G is (C₄, bull)-free if and only if it is a clique blowup of some graph of girth at least 5. As a consequence, we show that both the classes of (C₄, bull)-free graphs and (C₄, hammer)-free graphs are linear-Pollyannas.
No takes yet. Share an insight, caveat, or question.
Chen et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: