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. 217-227, János Bolyai Math. Soc., Budapest, 1994.
|