A note on the vertex arboricity of signed graphs

Weichan Liu, Chen Gong, Lifang Wu, Xin ZhangarXiv 2017 · OpenReview

TL;DR

This paper introduces and studies the concept of "signed vertex arboricity" for signed graphs, which generalizes the vertex arboricity of unsigned graphs. The authors prove that this new invariant is bounded by 3 for important classes of graphs, including balanced signed triangulations and edge-maximal $K_5$-minor-free graphs, extending known results for planar graphs.

What Problem Does This Paper Address?

The paper tackles the problem of extending the concept of vertex arboricity from standard (unsigned) graphs to signed graphs. Vertex arboricity, for an unsigned graph, is the minimum number of forests needed to cover its vertices such that each forest's induced subgraph is a forest. This concept is crucial in understanding graph structures and has applications in areas like network design. The authors aim to define and analyze a "signed version" of this property, which accounts for the positive and negative edge signs in signed graphs. This involves defining a "signed tree-coloring" and determining the minimum number of colors required for such a coloring, known as the signed vertex arboricity.

Methods

The core of the paper lies in defining and proving properties of "signed tree-coloring" and "signed vertex arboricity."

  • Signed Tree-Coloring: A vertex coloring $c$ of a signed graph $(G, \sigma)$ is a signed tree-coloring if for any color $i$ and any vertex $u$, the subgraph $G^c(i, \pm)$ is a forest. $G^c(i, \pm)$ is constructed using vertices colored $i$ or $-i$, with positive edges connecting vertices of the same color and negative edges connecting vertices of opposite colors.
  • Signed Vertex Arboricity ($va(G, \sigma)$): This is defined as the minimum integer $n$ for which a signed tree-$n$-coloring exists.
  • Switching Equivalence: The paper utilizes the concept of "switching" vertices in a signed graph, which involves flipping the signs of incident edges. They prove that switching equivalent signed graphs have the same signed vertex arboricity.
  • Inductive Proofs: Key results, particularly those bounding $va(G, \sigma)$ to 3, are established using induction on the graph's order or structure. This involves decomposing graphs into smaller components (e.g., using Lemma 3 for combining colorings of disjoint graphs) and applying previously established theorems or lemmas.
  • List Coloring: The proofs for bounding $va(G, \sigma)$ often employ a list coloring approach, where each vertex is assigned a list of allowed colors, and the goal is to find a valid coloring using these lists.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Generalization of Vertex Arboricity: The paper successfully extends the notion of vertex arboricity to signed graphs, providing a new invariant for this richer class of structures.
  • Robustness to Switching: The signed vertex arboricity is invariant under vertex switching, a fundamental operation in signed graph theory. This suggests that the property is structurally significant.
  • Boundedness for Important Graph Classes: The most significant finding is that the signed vertex arboricity is at most 3 for balanced signed triangulations and edge-maximal $K_5$-minor-free graphs. This is a strong structural result.
  • Connection to Planar Graphs: The result for triangulations directly generalizes the known bound of 3 for the vertex arboricity of planar graphs, highlighting the power of the signed graph framework.
  • Structural Decomposition: The proofs rely on clever graph decomposition techniques (e.g., splitting graphs at $K_2$ or $K_3$ intersections) and combining colorings of subgraphs, which is a common and powerful strategy in graph theory.

Key Results

  • Theorem 2: Two switching equivalent signed graphs have the same signed vertex arboricity ($va(G, \sigma) = va(G, \sigma')$).
  • Corollary 5: For any balanced signed triangulation $(G, \sigma)$, $va(G, \sigma) \leq 3$.
  • Corollary 7: For any planar graph $G$, $va(G) \leq 3$. (This is presented as a consequence of the triangulation result).
  • Theorem 11: For any edge-maximal $K_5$-minor-free graph $(G, \sigma)$ with a balanced signature, $va(G, \sigma) \leq 3$.
  • Corollary 12: For any $K_5$-minor-free graph $G$, $va(G) \leq 3$.

Limitations and Future Work

  • Focus on Balanced Graphs: The main results concerning the bound of 3 apply to balanced signed graphs. The behavior of signed vertex arboricity for unbalanced graphs is not explored.
  • Sharpness of the Bound: The paper notes that the bound of 3 is sharp for planar graphs (and by extension, for balanced signed triangulations), referencing existing work for unsigned graphs. However, it doesn't explicitly construct a signed graph that requires 3 colors for the broader class of $K_5$-minor-free graphs.
  • Further Exploration of $K_5$-minor-free Graphs: While the paper establishes a bound for edge-maximal $K_5$-minor-free graphs, further investigation into general $K_5$-minor-free graphs might be a natural next step.
  • Algorithmic Aspects: The paper focuses on the existence of such colorings and their bounds. Developing efficient algorithms for finding signed tree-colorings or computing the signed vertex arboricity could be a direction for future research.

Summary updated

Abstract

A signed tree-coloring of a signed graph $(G,\sigma)$ is a vertex coloring $c$ so that $G^{c}(i,\pm)$ is a forest for every $i\in c(u)$ and $u\in V(G)$, where $G^{c}(i,\pm)$ is the subgraph of $(G,\sigma)$ whose vertex set is the set of vertices colored by $i$ or $-i$ and edge set is the set of positive edges with two end-vertices colored both by $i$ or both by $-i$, along with the set of negative edges with one end-vertex colored by $i$ and the other colored by $-i$. If $c$ is a function from $V(G)$ to $M_n$, where $M_n$ is $\{\pm 1,\pm 2,\ldots,\pm k\}$ if $n=2k$, and $\{0,\pm 1,\pm 2,\ldots,\pm k\}$ if $n=2k+1$, then $c$ a signed tree-$n$-coloring of $(G,\sigma)$. The minimum integer $n$ such that $(G,\sigma)$ admits a signed tree-$n$-coloring is the signed vertex arboricity of $(G,\sigma)$, denoted by $va(G,\sigma)$. In this paper, we first show that two switching equivalent signed graphs have the same signed vertex arboricity, and then prove that $va(G,\sigma)\leq 3$ for every balanced signed triangulation and for every edge-maximal $K_5$-minor-free graph with balanced signature. This generalizes the well-known result that the vertex arboricity of every planar graph is at most 3.
BibTeX
@misc{liu2017note,
  author = {Weichan Liu and Chen Gong and Lifang Wu and Xin Zhang},
  title = {{A note on the vertex arboricity of signed graphs}},
  year = {2017},
  eprint = {1708.03077},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1708.03077},
}
Figure