Mathematics – Combinatorics
Scientific paper
2009-11-11
Mathematics
Combinatorics
Scientific paper
In a seminal paper, Alon and Tarsi have introduced an algebraic technique for proving upper bounds on the choice number of graphs (and thus, in particular, upper bounds on their chromatic number). The upper bound on the choice number of $G$ obtained via their method, was later coined the \emph{Alon-Tarsi number of $G$} and was denoted by $AT(G)$. They have provided a combinatorial interpretation of this parameter in terms of the eulerian subdigraphs of an appropriate orientation of $G$. Their characterization can be restated as follows. Let $D$ be an orientation of $G$. Assign a weight $\omega_D(H)$ to every subdigraph $H$ of $D$: if $H \subseteq D$ is eulerian, then $\omega_D(H) = (-1)^{e(H)}$, otherwise $\omega_D(H) = 0$. Alon and Tarsi proved that $AT(G) \leq k$ if and only if there exists an orientation $D$ of $G$ in which the out-degree of every vertex is strictly less than $k$, and moreover $\sum_{H \subseteq D} \omega_D(H) \neq 0$. Shortly afterwards, for the special case of line graphs of $d$-regular $d$-edge-colorable graphs, Alon gave another interpretation of $AT(G)$, this time in terms of the signed $d$-colorings of the line graph. In this paper we generalize both results. The first characterization is generalized by showing that there is an infinite family of weight functions (which includes the one considered by Alon and Tarsi), each of which can be used to characterize $AT(G)$. The second characterization is generalized to all graphs (in fact the result is even more general -- in particular it applies to hypergraphs). We then use the second generalization to prove that $\chi(G) = ch(G) = AT(G)$ holds for certain families of graphs $G$. Some of these results generalize certain known choosability results.
No associations
LandOfFree
On two generalizations of the Alon-Tarsi polynomial method does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On two generalizations of the Alon-Tarsi polynomial method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On two generalizations of the Alon-Tarsi polynomial method will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-533552