# 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\).