Beyond degree choosability (Q2401410)

Summary: Let \(G\) be a connected graph with maximum degree \(\Delta\). Brooks' theorem states that \(G\) has a \(\Delta\)-coloring unless \(G\) is a complete graph or an odd cycle. A graph \(G\) is degree-choosable if \(G\) can be properly colored from its lists whenever each vertex \(v\) gets a list of \(d(v)\) colors. In the context of list coloring, Brooks' theorem can be strengthened to the following. Every connected graph \(G\) is degree-choosable unless each block of \(G\) is a complete graph or an odd cycle; such a graph \(G\) is a Gallai tree. This degree-choosability result was further strengthened to Alon-Tarsi orientations; these are orientations of \(G\) in which the number of spanning Eulerian subgraphs with an even number of edges differs from the number with an odd number of edges. A graph \(G\) is degree-AT if \(G\) has an Alon-Tarsi orientation in which each vertex has indegree at least 1. \textit{N. Alon} and \textit{M. Tarsi} [Combinatorica 12, No. 2, 125--134 (1992; Zbl 0756.05049)] showed that if \(G\) is degree-AT, then \(G\) is also degree-choosable. \textit{J. Hladký} et al. [Discrete Math. 310, No. 23, 3426--3428 (2010; Zbl 1222.05061)] showed that a connected graph is degree-AT if and only if it is not a Gallai tree. In this paper, we consider pairs \((G,x)\) where \(G\) is a connected graph and \(x\) is some specified vertex in \(V(G)\). We characterize pairs such that \(G\) has no Alon-Tarsi orientation in which each vertex has indegree at least 1 and \(x\) has indegree at least 2. When \(G\) is 2-connected, the characterization is simple to state.