Hitting all maximum stable sets in P₅-free graphs

DOI10.1016/J.JCTB.2023.11.005zbMATH Open1530.05144arXiv2302.04986MaRDI QIDQ6187345FDOQ6187345

Authors: Sepehr Hajebi, Yanjia Li, Sophie Spirkl 

Publication date: 15 January 2024

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: We prove that every $P_5$-free graph of bounded clique number contains a small hitting set of all its maximum stable sets. More generally, let us say a class $mathcalC$ of graphs is $eta$-bounded if there exists a function $h:mathbbNightarrowmathbbN$ such that $eta(G)leqh(omega(G))$ for every graph $GinmathcalC$, where $eta(G)$ denotes smallest cardinality of a hitting set of all maximum stable sets in $G$, and $omega(G)$ is the clique number of $G$. Also, $mathcalC$ is said to be polynomially $eta$-bounded if in addition $h$ can be chosen to be a polynomial. We introduce $eta$-boundedness inspired by a question of Alon and motivated by a number of meaningful similarities to $chi$-boundedness. In particular, we propose an analogue of the Gy'{a}rf'{a}s-Sumner conjecture, that the class of all $H$-free graphs is $eta$-bounded if (and only if) $H$ is a forest. Like $chi$-boundedness, the case where $H$ is a star is easy to verify, and we prove two non-trivial extensions of this: $H$-free graphs are $eta$-bounded if (1) $H$ has a vertex incident with all edges of $H$, or (2) $H$ can be obtained from a star by subdividing at most one edge, exactly once. Unlike $chi$-boundedness, the case where $H$ is a path is surprisingly hard. Our main result mentioned at the beginning shows that $P_5$-free graphs are $eta$-bounded. The proof is rather involved compared to the classical ``Gy'{a}rf'{a}s path argument which establishes, for all $t$, the $chi$-boundedness of $P_t$-free graphs. It remains open whether $P_t$-free graphs are $eta$-bounded for $tgeq6$. It also remains open whether $P_5$-free graphs are polynomially $eta$-bounded, which, if true, would imply the ErdH{o}s-Hajnal conjecture for $P_5$-free graphs. But we prove that $H$-free graphs are polynomially $eta$-bounded if $H$ is a proper induced subgraph of $P_5$.

Full work available at URL: https://arxiv.org/abs/2302.04986

zbMATH Keywords

Ramsey theoryinduced subgraphsindependent sets

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• Graph Theory and Probability
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• A characterization of perfect graphs
• Title not available (Why is that?)
• Radius two trees specify χ‐bounded classes
• Ramsey-type theorems
• A bound on the chromatic number of graphs without certain induced subgraphs
• On hitting all maximum cliques with an independent set
• A Theorem on k-Saturated Graphs
• Title not available (Why is that?)
• Even-hole-free graphs still have bisimplicial vertices
• Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
• A survey of \(\chi\)-boundedness
• Polynomial bounds for chromatic number II: Excluding a star‐forest

This page was built for publication: Hitting all maximum stable sets in \(P_5\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187345)