Aboulker–Aubian–Charbit–Lopes conjecture on forest backedge graphs

About 2 years old · traced to

Let TT be a tournament and suppose that one of its backedge graphs is a forest. For a tournament, let its clique number mean the minimum clique number of a backedge graph over all vertex orderings, and let its dichromatic number be the minimum number of acyclic vertex classes in a partition. Aboulker–Aubian–Charbit–Lopes conjecture. For every k∈Nk\in\mathbb N, the class of tournaments not containing TT as a subtournament and having clique number at most kk has bounded dichromatic number. The paper announces a counterexample and proves that this conjecture is false.

References

Primary source

Guillaume Aubian, “Computing the clique number of tournaments”, arXiv:2401.07776 (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.