Upper bound on clique transversal number
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\).
Denote by \( R(n)\) the largest integer such that every trianglefree graph on \( n\) vertices contains an independent set of \( R(n)\) vertices. Is it true that \( \tau(G) \leq n R(n)\)?
From the results on the Ramsey numbers \( r(3,k)\), we know that \( c \sqrt {n \log n} < R(n) < c' \sqrt {n \log n}\). So far, the best current bound [1] is \( \tau(G) \leq n \sqrt{2n}+c\) for a small constant \( c\).
Erdös[2] asked the following additional questions on \( g(n)=\max \tau (G)\), where \( G\) ranges over all graphs on \( n\) vertices:
Problem
Is it true that \( \tau(G) < ng(n) \sqrt n \) and \(g(n) \rightarrow \infty \) as \(n \rightarrow \infty\) ?
Bibliography  

1 
P. Erdös, T. Gallai and Zs. Tuza, Covering the cliques of a graph with
vertices,Topological, Algebraical and Combinatorial Structures, Frolík's memorial volume, Discrete Math. 108 (1992), 279289.

2  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.
