Clique transversal number is sublinear for graphs with no small cliques
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
Let \( \tau(G)\) denote the cardinality of a smallest set of vertices in \( G\) that shares some vertex with every clique of \( G\).
Problem [1]
Suppose all cliques in \(G\) have \(cn\) vertices. Is it true that \[ \tau(G) = o(n)? \]
Bibliography  

1  P. Erdös. Problems and results on set systems and hypergraphs, Extremal problems for finite sets (Visegrád, 1991), Bolyai Soc. Math. Stud., 3, pp. 217227, János Bolyai Math. Soc., Budapest, 1994.
