Geodesic
Piercing independent sets in graphs without large induced matching
Jiangdong Ai1 ; Hong Liu2 ; Zixiang Xu3 ; Qiang Zhou4
1Nankai University
2Institute for Basic Science
3Extremal Combinatorics and Probability Group, Institute for Basic Science
4Chinese Academy of Sciences
The electronic journal of combinatorics, Tome 32 (2025) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Given a graph $G$, denote by $h(G)$ the smallest size of a subset of $V(G)$ which intersects every maximum independent set of $G$. We prove that any graph $G$ without induced matching of size $t$ satisfies $h(G)\le \omega(G)^{3t-3+o(1)}$. This resolves a conjecture of Hajebi, Li and Spirkl [Hitting all maximum stable sets in $P_{5}$-free graphs. J. Combin. Theory Ser. B, 165:142-163, 2024].
DOI : 10.37236/13469
Classification : 05C69, 05C70

Jiangdong Ai  1   ; Hong Liu  2   ; Zixiang Xu  3   ; Qiang Zhou  4

1 Nankai University
2 Institute for Basic Science
3 Extremal Combinatorics and Probability Group, Institute for Basic Science
4 Chinese Academy of Sciences 
@article{10_37236_13469,
     author = {Jiangdong Ai and Hong Liu and Zixiang Xu and Qiang Zhou},
     title = {Piercing independent sets in graphs without large induced matching},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {1},
     doi = {10.37236/13469},
     zbl = {1559.05139},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/13469/}
}
TY  - JOUR
AU  - Jiangdong Ai
AU  - Hong Liu
AU  - Zixiang Xu
AU  - Qiang Zhou
TI  - Piercing independent sets in graphs without large induced matching
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/13469/
DO  - 10.37236/13469
ID  - 10_37236_13469
ER  - 
%0 Journal Article
%A Jiangdong Ai
%A Hong Liu
%A Zixiang Xu
%A Qiang Zhou
%T Piercing independent sets in graphs without large induced matching
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/13469/
%R 10.37236/13469
%F 10_37236_13469
Jiangdong Ai; Hong Liu; Zixiang Xu; Qiang Zhou. Piercing independent sets in graphs without large induced matching. The electronic journal of combinatorics, Tome 32 (2025) no. 1. doi: 10.37236/13469

Cité par Sources :