Sublinear Hitting Sets for Some Geometric Graphs

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 the 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:

1. 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(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.
2. 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.
3. We show the conjecture holds for those hereditary graphs having sublinear balanced separators. We also show that h(G) can be upper bounded by constants for several sporadic families of graphs with large independence numbers.