χ-Mader bound for oriented trees

Status solved medium confidence

Conjecture 11 states that for every oriented tree T of order k, mader_chi(T) <= 2k-2. The 2020 paper arXiv:2008.09888 (Gishboliner, Steiner, Szabó) proves the stronger result mader_chi(F) = v(F) for all orientations of cactus graphs (Corollary 8 per internal references); since every tree is a cactus graph (trees have no cycles, so the cactus condition is vacuously satisfied), this implies mader_chi(T) = k <= 2k-2 for every oriented tree T of order k >= 2, resolving Conjecture 11. The abstract of 2008.09888 confirms results for orientations of cactus graphs and bioriented forests, consistent with this claim.

Cited literature (1)

• proof Dichromatic number and forced subdivisions (2020)
  Lior Gishboliner, Raphael Steiner, Tibor Szabó · arXiv preprint · arXiv:2008.09888

  Proves mader_chi(F) = v(F) for every octus digraph F (Theorem 7) and every orientation of a cactus graph (Corollary 8); since trees are special cases of cactus graphs, this resolves Conjecture 11 with the sharper equality mader_chi(T) = k, which in particular satisfies the conjectured bound k <= 2k-2.

Reviewer notes. Trees are special cases of cactus graphs (a cactus graph is connected with every edge on at most one simple cycle; trees have no cycles, so they satisfy this vacuously). If arXiv:2008.09888 Corollary 8 proves mader_chi(F) = v(F) for every orientation of a cactus graph, Conjecture 11 is resolved with the sharper bound mader_chi(T) = k. Confidence is medium rather than high because the full PDF was unreadable via WebFetch and the conclusion rests on the abstract wording plus two internal-reference entries (fuzz 75 and 70) that agree on the cactus-graph corollary. A follow-up paper arXiv:2210.06247 (2022, 'Some Mader-perfect graph classes') extends the Mader-perfect class beyond octi digraphs but was not directly verified against Conjecture 11.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).