The characterization conjecture for 2-extremal digraphs

Let H2\mathcal H_2 be the smallest class of digraphs containing symmetric odd cycles and closed under taking directed Hajós joins and 22-Hajós tree joins. A digraph is 22-extremal when it has the relevant extremal colouring property defined in the paper. Characterization conjecture. A digraph is 22-extremal if and only if it belongs to H2\mathcal H_2. The paper observes that digraphs in H2\mathcal H_2 are 22-extremal; the converse, which would characterize all 22-extremal digraphs, remains conjectural.

Sources & referencesView supporting material

Primary source

Pierre Aboulker, Guillaume Aubian and Pierre Charbit, “Digraph Colouring and Arc-Connectivity”, arXiv:2304.04690 (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.