The optimal-size clique transversal conjecture for 4-chordal graphs

Let GG be a chordal graph with nn vertices. Call GG 4-chordal if every edge of GG is contained in a clique with four vertices, and call a set of vertices UU a clique transversal if it meets every non-trivial maximal clique of GG.

Optimal-size clique transversal conjecture. Every 44-chordal graph with nn vertices has a clique transversal of size at most 2n/72n/7.

The question generalizes known bounds for 22- and 33-chordal graphs. Andreae and Flotow constructed arbitrarily large examples requiring at least 2n/7O(1)2n/7-O(1) vertices, suggesting that the bound is asymptotically tight; the paper proves the stronger integral bound 2(n1)/72(n-1)/7 for n5n\geq 5.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.