The degeneracy and Alon-Tarsi number under $F$-sum operations

Abstract

The Alon-Tarsi number of a graph $G$ is the smallest $k$ such that there exists an orientation $D$ of $G$ with maximum outdegree $k-1$ satisfying that the number of even Eulerian subgraphs is different from the number of odd Eulerian subgraphs. The degeneracy of a graph $G$ is the maximum value of the minimum degree over all subgraphs of $G$. In this paper, we obtain a characterization of graphs with $AT(G)=2$ for any graph $G$, and study the Alon-Tarsi number of $F$-sum in terms of degeneracy.