2024/04/16 by Xinbu Cheng, Cheng, Xinbu, Huang, Xinqi +2
Computer Science · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2404.10379
openalex publication_date 2024/04/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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: \beginenumerate \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(\fracnlogn) 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)≤ O(√(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. \endenumerate We also show that h(G) can be upper bounded by constants for several sporadic families of graphs with large independence numbers.