Estimate the clique transversal number of a graph
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
A problem on clique transversals (proposed by Erdös, Gallai and Tuza[1])
Estimate the cardinality, denoted by \(\tau(G)\), 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 triangle-free 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\).