1 citations · 1 across the 6 of their papers we have counts for
5 papers · 1 filter
Clique density vs blowups
Domagoj Bradač, Hong Liu, Zhuo Wu +1
A well-known theorem of Nikiforov asserts that any graph with a positive -density contains a logarithmic blowup of . In this paper, we explore variants of Nikiforov's r…
Bollobás-Erdős-Tuza conjecture for graphs with no induced
Xinbu Cheng, Zixiang Xu
A widely open conjecture proposed by Bollobás, Erdős, and Tuza in the early 1990s states that for any -vertex graph , if the independence number , then there is…
Sublinear hitting sets for some geometric graphs
Xinbu Cheng, Xinqi Huang, Mingyuan Rong +1
For an -vertex graph , let denote the smallest size of a subset of such that it intersects every maximum independent set of . A conjecture posed by Bollobás,…
Piercing independent sets in graphs without large induced matching
Jiangdong Ai, Hong Liu, Zixiang Xu +1
Given a graph , denote by the smallest size of a subset of which intersects every maximum independent set of . We prove that any graph without induced match…
Beyond chromatic threshold via the -theorem, and a sharp blow-up phenomenon
Hong Liu, Chong Shangguan, Jozef Skokan +1
We establish a novel connection between the well-known chromatic threshold problem in extremal combinatorics and the celebrated -theorem in discrete geometry. In particular,…