Hameed's conjecture on semi-transitivity of Mycielski graphs

Let GG be a graph, and let μ(G)\mu(G) denote its Mycielski graph. A graph is semi-transitive if it admits an acyclic orientation with no shortcut. Hameed's conjecture. For every graph GG, the graph μ(G)\mu(G) is semi-transitive if and only if GG is a bipartite graph. Hameed proved this equivalence when GG is a comparability graph, while the assertion for arbitrary graphs remains open.

Sources & referencesView supporting material

Primary source

Sergey Kitaev and Artem Pyatkin, “A note on semi-transitivity of Mycielski graphs”, arXiv:2408.05066 (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.