EUVIMEDEUVIMED entdecken
Crossref

Structure and linear-Pollyanna for some square-free graphs

Ran Chen, Baogang Xu

Discrete Mathematics · 2026-06 · 349 (6) · 114979

DOI: 10.1016/j.disc.2026.114979 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics, 2026-06. Verfasst von Ran Chen und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 24 Literaturangaben. Gefördert von: National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We use $P_t$ and $C_t$ to denote a path and a cycle on $t$ vertices, respectively. A {\em bull} is a graph consisting of a triangle with two disjoint pendant edges, a {\em hammer} is a graph obtained by identifying an endvertex of a $P_3$ with a vertex of a triangle. A class ${\cal F}$ is $\chi$-bounded if there is a function $f$ such that $\chi(G)\leq f(\omega(G))$ for all induced subgraphs $G$ of a graph in ${\cal F}$. A class ${\cal C}$ of graphs is {\em Pollyanna} (resp. {\em linear-Pollyanna}) if ${\cal C}\cap {\cal F}$ is polynomially (resp. linear-polynomially) $\chi$-bounded for every $\chi$-bounded class ${\cal F}$ of graphs. Chudnovsky {\em et al} \cite{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_4$, hammer)-free if and only if it has girth at least 5, and $G$ is $(C_4$, 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_4$, bull)-free graphs and $(C_4$, hammer)-free graphs are linear-Pollyannas.

Förderung

  • National Natural Science Foundation of China

Zitieren

APA

Chen, R., & Xu, B. (2026). Structure and linear-Pollyanna for some square-free graphs. Discrete Mathematics, 349(6), 114979. https://doi.org/10.1016/j.disc.2026.114979

Vancouver

Chen R, Xu B. Structure and linear-Pollyanna for some square-free graphs. Discrete Mathematics. 2026;349(6):114979. doi:10.1016/j.disc.2026.114979

BibTeX
@article{Chen2026,
  author = {Chen, Ran and Xu, Baogang},
  title = {Structure and linear-Pollyanna for some square-free graphs},
  journal = {Discrete Mathematics},
  year = {2026},
  volume = {349},
  number = {6},
  pages = {114979},
  doi = {10.1016/j.disc.2026.114979}
}
Kostenlos starten →