Alon-Tarsi orientation with half out-degree

Question 6.1 · arXiv:2209.09107

arXiv Question high confidence— first stated 2024-06-20

Authors: Peter Bradshaw, Yaobin Chen, Hao Ma, Bojan Mohar, Hehui Wu

Status open high confidence

Question 6.1 from arXiv:2209.09107 asks whether every graph G has a spanning subgraph admitting an Alon-Tarsi orientation in which each vertex v has out-degree at least (deg_G(v)-1)/2; an affirmative answer would prove Conjecture 1.1 for all graphs via Theorem 1.4 and give AT(H) ≤ ⌊(Δ+3)/2⌋ for a dense subgraph H. No resolution or partial progress on this specific question has been found in the literature indexed since the paper's 2024 publication.

Reviewer notes. No follow-up found after 5 web searches. The two most relevant nearby papers — arXiv:2406.05095 (Henderschedt–McDonald, forbidden out-degrees in regular graphs) and arXiv:2509.00657 (Cho–Choi–Park–Zhu, AT-extendability of sparse graphs) — address related but distinct problems and do not mention Question 6.1. The question was posed in June 2024 and remains open with high confidence.

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

Question. Does every graph $G$ have a spanning subgraph with an Alon-Tarsi orientation in which each vertex $v$ has out-degree at least $\frac{1}{2}(\deg_{G}(v)-1)$?

Context

This question asks whether Conjecture 1.1 could be proved for every graph via the paper's Theorem 1.4 by finding a suitable Alon-Tarsi orientation, which would yield a stronger result. An affirmative answer would further imply that every graph $G$ on $n$ vertices and maximum degree $\Delta$ has a subgraph $H$ with at least $|E(G)|-n/2$ edges satisfying $\operatorname{AT}(H)\leq\lfloor\frac{1}{2}\Delta+\frac{3}{2}\rfloor$.

Source paper

List-avoiding orientations
Peter Bradshaw, Yaobin Chen, Hao Ma, Bojan Mohar, Hehui Wu · 2024-06-20
https://arxiv.org/abs/2209.09107