Matching reducing Alon-Tarsi number to ½Δ

Question 6.2 · 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.2 asks whether there exists a constant $C$ such that every graph $G$ of maximum degree $\Delta$ has a matching $M$ with $\operatorname{AT}(G-M)\leq\frac{1}{2}\Delta+C$. No follow-up paper resolving this question was found in targeted searches through May 2026. The question is motivated by Grytczuk--Zhu's result for planar graphs and the known lower bound showing $C$ cannot be smaller than $\frac{1}{2}$ (from $K_n$ with a maximum matching).

Reviewer notes. No follow-up paper resolving Question 6.2 was found. The source paper was published in Combinatorica (2024). The conjecture is closely related to Grytczuk--Zhu's theorem (arXiv:1811.12012) that every planar graph G has a matching M with AT(G-M) ≤ 4, and to Huang et al.'s result that AT(K_n - N) = ⌈n/2⌉ for a maximum matching N in K_n, which establishes the lower bound C ≥ 1/2.

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

Question. Does there exist a constant $C$ such that every graph $G$ of maximum degree $\Delta$ has a matching $M$ such that $\operatorname{AT}(G-M)\leq\frac{1}{2}\Delta+C$?

Context

This question is motivated by results showing that removing a matching from a graph can reduce upper bounds on coloring parameters such as the Alon-Tarsi number. It is noted that $C$ cannot be smaller than $\frac{1}{2}$, since for any odd $n$ and any maximum matching $M$ in $K_n$, $\operatorname{AT}(K_n-M)=\frac{n+1}{2}$. The authors ask specifically about matchings, inspired by Zhu's result on planar graphs and the result of Grytczuk and Zhu.

Source paper

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