Hitting all maximum stable sets in P₅-free graphs

DOI10.1016/J.JCTB.2023.11.005MaRDI QIDQ6187345zbMATHFDO

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)

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

Ramsey theory induced subgraphs independent sets

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)

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

m a t h c a l C

of graphs is

e t a

-bounded if there exists a function

h : m a t h b b N i g h t a r r o w m a t h b b N

such that

e t a (G) l e q h (o m e g a (G))

for every graph

G i n m a t h c a l C

, where

e t a (G)

denotes smallest cardinality of a hitting set of all maximum stable sets in

G

, and

o m e g a (G)

is the clique number of

G

. Also,

m a t h c a l C

is said to be polynomially

e t a

-bounded if in addition

h

can be chosen to be a polynomial. We introduce

e t a

-boundedness inspired by a question of Alon and motivated by a number of meaningful similarities to

c h i

-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

e t a

-bounded if (and only if)

H

is a forest. Like

c h i

-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

e t a

-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

c h i

-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

e t a

-bounded. The proof is rather involved compared to the classical ``Gy'{a}rf'{a}s path argument which establishes, for all $t$ , the $c h i$ -boundedness of $P_{t}$ -free graphs. It remains open whether $P_{t}$ -free graphs are $e t a$ -bounded for $t g e q 6$ . It also remains open whether $P_{5}$ -free graphs are polynomially $e t a$ -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 $e t a$ -bounded if $H$ is a proper induced subgraph of $P_{5}$ .

Recommendations

Cites work

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)