Kempe-equivalence characterization of perfectly contractile graphs
Kempe-equivalence characterization of perfectly contractile graphs
Let be a perfect graph. A replication graph of an induced subgraph of is obtained by replacing vertices of that induced subgraph by replicated vertices as defined in the paper. A -coloring is a proper coloring using colors, and two -colorings are Kempe equivalent if one can be obtained from the other by Kempe changes. The chromatic number of is denoted by .
Kempe-equivalence conjecture. The graph is perfectly contractile if and only if, for every replication graph of an arbitrary induced subgraph of and every , all -colorings of 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.