The optimal-size clique transversal conjecture for 4-chordal graphs
The optimal-size clique transversal conjecture for 4-chordal graphs
Let be a chordal graph with vertices. Call 4-chordal if every edge of is contained in a clique with four vertices, and call a set of vertices a clique transversal if it meets every non-trivial maximal clique of .
Optimal-size clique transversal conjecture. Every -chordal graph with vertices has a clique transversal of size at most .
The question generalizes known bounds for - and -chordal graphs. Andreae and Flotow constructed arbitrarily large examples requiring at least vertices, suggesting that the bound is asymptotically tight; the paper proves the stronger integral bound for .
Sources & referencesView supporting material
Primary source
Jacob W. Cooper, Andrzej Grzesik and Daniel Kral, “Optimal-size clique transversals in chordal graphs”, arXiv:1601.05305 (2018).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.