Kempe-equivalence characterization of perfectly contractile graphs

Let GG be a perfect graph. A replication graph HH of an induced subgraph of GG is obtained by replacing vertices of that induced subgraph by replicated vertices as defined in the paper. A kk-coloring is a proper coloring using kk colors, and two kk-colorings are Kempe equivalent if one can be obtained from the other by Kempe changes. The chromatic number of HH is denoted by 4χ(H)44\chi(H)4.

Kempe-equivalence conjecture. The graph GG is perfectly contractile if and only if, for every replication graph HH of an arbitrary induced subgraph of GG and every kχ(H)k \geq \chi(H), all kk-colorings of HH are Kempe equivalent.

This would characterize perfectly contractile perfect graphs through the behavior of colorings of their replication graphs. The conjecture is presented as a new characterization, and the source gives no evidence that it has been resolved.

Sources & referencesView supporting material

Primary source

Hidefumi Ohsugi and Akiyoshi Tsuchiya, “Kempe equivalence and quadratic toric rings”, arXiv:2303.12824 (2026).

Additional references

3 papers in this index state this conjecture (2021–2023). The statement above is taken from the most recent of them; the others are arXiv:2207.13244, arXiv:2102.07948.

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.