Alon-Tarsi number of signed planar graphs

Wei Wang, Jianguo QianarXiv 2018 · DOI · arXiv

Abstract

Let $(G,σ)$ be any signed planar graph. We show that the Alon-Tarsi number of $(G,σ)$ is at most 5, generalizing a recent result of Zhu for the unsigned case. In addition, if $(G,σ)$ is 2-colorable then $(G,σ)$ has the Alon-Tarsi number at most 4. We also construct a signed planar graph which is 2-colorable but not 3-choosable.

Introduction

In the realm of algebraic graph theory, the Alon-Tarsi number ($AT$) serves as a powerful upper bound for the list chromatic number, or choosability, of a graph. While the properties of unsigned planar graphs are well-documented—specifically that $AT(G) \leq 5$—the extension of these results to signed graphs introduces significant complexity. A signed graph $(G, \sigma)$ assigns a sign $\sigma(uv) \in \{+1, -1\}$ to each edge $uv$. A proper coloring $\phi$ in this context requires that $\phi(u) \neq \sigma(uv)\phi(v)$. This paper by Wei Wang and Jianguo Qian provides a significant generalization of planar graph coloring results to the world of signed graphs.

Theoretical Framework and Methods

The authors bridge algebraic and combinatorial methods to establish their bounds. Central to their approach is the Combinatorial Nullstellensatz, which allows them to relate the non-vanishing coefficients of a specialized graph polynomial $P_{G,\sigma}(x)$ to the graph's coloring properties.

Orientation and Eulerian Subgraphs

A key combinatorial characterization used is the relationship between the Alon-Tarsi number and graph orientations. For a signed graph, the $AT$ number is determined by finding an orientation $D$ such that the out-degree of each vertex $v$ is less than a specified value $k_v$, and the number of "$\sigma$-even" Eulerian subdigraphs differs from the number of "$\sigma$-odd" ones. This refinement accounts for the parity of negative edges within the subgraphs.

Inductive Structural Proofs

To prove the main theorem for planar graphs, the authors utilize induction on the number of vertices, focusing on "near triangulations"—planar graphs where every interior face is a triangle. They analyze various configurations of the boundary cycle to construct "$\sigma$-nice" orientations.

Figure 1: Decomposition of a planar graph into subgraphs $G_1$ and $G_2$ by a chord $v_k v_j$.

As shown in Figure 1, a common technique involves splitting the graph along a chord to apply inductive hypotheses to smaller components. The proof of Theorem 1.4 involves a detailed case analysis of the boundary structure, as illustrated in the following composite figure.

Figure 6: Various structural cases (a-d) used in the inductive proof to establish the Alon-Tarsi bound for signed planar graphs.

Key Results and Insights

The paper yields several landmark results in signed graph theory:

  • Universal Bound for Signed Planar Graphs: Theorem 1.4 establishes that for any signed planar graph $(G, \sigma)$, $AT(G, \sigma) \leq 5$. This directly implies that all such graphs are 5-choosable, successfully extending Zhu's result for unsigned graphs.
  • Bound for 2-Colorable Graphs: For the subclass of 2-colorable (bipartite-like) signed planar graphs, the bound is tightened to $AT(G, \sigma) \leq 4$.
  • The Choosability Gap: Perhaps the most surprising finding is the divergence between colorability and choosability in signed graphs. In the unsigned world, every 2-colorable planar graph is 3-choosable. However, the authors construct a specific 2-colorable signed graph (specifically a "negative" graph where all edges are -1) that is not 3-choosable. This demonstrates that the Alon-Tarsi bound of 4 is necessary and that signed graphs possess structural nuances absent in their unsigned counterparts.

Conclusion and Future Directions

This work reinforces the Alon-Tarsi number as a robust invariant that persists under graph "switching" (negating all edges incident to a vertex). While the bound of 5 is tight for general planar graphs, future research might investigate if the bound of 4 for 2-colorable graphs can be further refined for specific sub-families. Additionally, extending these algebraic techniques to graphs embedded on higher-genus surfaces remains a fertile ground for exploration.

Summary updated

Abstract

Let $(G,σ)$ be any signed planar graph. We show that the Alon-Tarsi number of $(G,σ)$ is at most 5, generalizing a recent result of Zhu for unsigned case. In addition, if $(G,σ)$ is $2$-colorable then $(G,σ)$ has the Alon-Tarsi number at most 4. We also construct a signed planar graph which is $2$-colorable but not $3$-choosable.
BibTeX
@misc{wang2018alon,
  author = {Wei Wang and Jianguo Qian},
  title = {{Alon-Tarsi number of signed planar graphs}},
  year = {2018},
  eprint = {1809.02907},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1809.02907},
}
Figure