Beyond degree choosability

Daniel W. Cranston¹ ; Landon Rabern²

¹Virginia Commonwealth University
²Franklin & Marshall

The electronic journal of combinatorics, Tome 24 (2017) no. 3

Résumé

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. Alon and Tarsi showed that if $G$ is degree-AT, then $G$ is also degree-choosable. Hladký, Král', and Schauz 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.

Détail

DOI : 10.37236/6179

Classification : 05C15, 05C40, 05C05
Mots-clés : list coloring, choosability, degree-choosable, Alon-Tarsi orientation, Gallai tree