The chordal graph representation conjecture for clique and reduced clique graphs

About 3 years old · traced to

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 G′G' 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.

References

Primary source

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

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.