Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2404.10379 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929616208265216 |
|---|---|
| author | Cheng, Xinbu Huang, Xinqi Rong, Mingyuan Xu, Zixiang |
| author_facet | Cheng, Xinbu Huang, Xinqi Rong, Mingyuan Xu, Zixiang |
| contents | For an $n$-vertex graph $G$, let $h(G)$ denote the smallest size of a subset of $V(G)$ such that it intersects every maximum independent set of $G$. A conjecture posed by Bollobás, Erdős and Tuza in early 90s remains widely open, asserting that for any $n$-vertex graph $G$, if the independence number $α(G) =Ω(n) $, then $h(G) = o(n)$. In this paper, we establish the validity of this conjecture for various classes of graphs, Our main contributions include: \begin{enumerate}
\item We provide a novel unified framework to find sub-linear hitting sets for graphs with certain locally sparse properties. Based on this framework, we can find hitting sets of size at most $O(\frac{n}{\log{n}})$ in any $n$-vertex even-hole-free graph (in particular, chordal graph) and in any $n$-vertex disk graph, with linear independence numbers.
\item Utilizing geometric observations and combinatorial arguments, we show that any $n$-vertex circle graph $G$ with linear independence number satisfies $h(G)\le O(\sqrt{n})$. Moreover, we extend this methodology to more general classes of graphs.
\item We show the conjecture holds for those hereditary graphs having sublinear balanced separators. \end{enumerate}
We also show that $h(G)$ can be upper bounded by constants for several sporadic families of graphs with large independence numbers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_10379 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sublinear hitting sets for some geometric graphs Cheng, Xinbu Huang, Xinqi Rong, Mingyuan Xu, Zixiang Combinatorics 05C69 For an $n$-vertex graph $G$, let $h(G)$ denote the smallest size of a subset of $V(G)$ such that it intersects every maximum independent set of $G$. A conjecture posed by Bollobás, Erdős and Tuza in early 90s remains widely open, asserting that for any $n$-vertex graph $G$, if the independence number $α(G) =Ω(n) $, then $h(G) = o(n)$. In this paper, we establish the validity of this conjecture for various classes of graphs, Our main contributions include: \begin{enumerate} \item We provide a novel unified framework to find sub-linear hitting sets for graphs with certain locally sparse properties. Based on this framework, we can find hitting sets of size at most $O(\frac{n}{\log{n}})$ in any $n$-vertex even-hole-free graph (in particular, chordal graph) and in any $n$-vertex disk graph, with linear independence numbers. \item Utilizing geometric observations and combinatorial arguments, we show that any $n$-vertex circle graph $G$ with linear independence number satisfies $h(G)\le O(\sqrt{n})$. Moreover, we extend this methodology to more general classes of graphs. \item We show the conjecture holds for those hereditary graphs having sublinear balanced separators. \end{enumerate} We also show that $h(G)$ can be upper bounded by constants for several sporadic families of graphs with large independence numbers. |
| title | Sublinear hitting sets for some geometric graphs |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2404.10379 |