The chordal graph representation conjecture for clique and reduced clique graphs

From papers

Let C(G)C(G) denote the clique graph of a graph GG, and let CR(G)C_R(G) denote its reduced clique graph. A graph is chordal if it has no induced cycle of length at least four.

Chordal graph representation conjecture. Let HH be a chordal graph. There are chordal graphs GG and GG' such that HH is isomorphic to both C(G)C(G) and CR(G)C_R(G').

The conjecture would establish that every chordal graph is simultaneously a clique graph and a reduced clique graph of chordal graphs. The source reports this as an open conjecture, while noting that a polynomial-time recognition algorithm is known for clique graphs of chordal graphs.

Progress summary

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

Sources & referencesView supporting material

Primary source

Dillon Mayhew and Andrew Probert, “Reduced clique graphs: a correction to "Chordal graphs and their clique graphs"”, arXiv:2301.03781 (2024).

Solutions 0

No solutions have been posted yet.