The polynomial-time recognition conjecture for reduced clique graphs of chordal graphs

For a graph GG, 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. The recognition problem asks whether a given graph is isomorphic to CR(G)C_R(G) for some chordal graph GG.

Reduced clique graph recognition conjecture. There is a polynomial-time algorithm for deciding whether a given graph is isomorphic to CR(G)C_R(G) for some chordal graph GG.

Polynomial-time recognition is known for clique graphs of chordal graphs, but the source says that the corresponding techniques do not obviously extend to reduced clique graphs. The conjectured algorithm is therefore presented as an open problem.

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).

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.