The chordal graph representation conjecture for clique and reduced clique graphs
Let denote the clique graph of a graph , and let 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 be a chordal graph. There are chordal graphs and such that is isomorphic to both and .
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
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.