The permutation-representation conjecture for comparability graphs

Let GG be a comparability graph, meaning the graph of a partial order. Write R2\mathcal{R}_2 for the class of graphs with representation number at most two, and R3p\mathcal{R}^p_{\le 3} for the class of graphs with permutation-representation number at most three. Permutation-representation conjecture. If

GR2,G\in\mathcal{R}_2,

then

GR3p.G\in\mathcal{R}^p_{\le 3}.

This conjecture proposes that every comparability graph with representation number at most two has permutation-representation number at most three. It is presented as an observation-based conjecture in the paper; no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Khyodeno Mozhui and K. V. Krishna, “Words for the Graphs with Permutation-Representation Number at most Three”, arXiv:2307.00301 (2023).

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.