Kempe-equivalence characterization of perfectly contractile graphs

About 5 years old · traced to

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.

References

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.