Variable degeneracy of graphs with restricted structures

Qianqian Wang, Tao Wang, Xiaojing YangarXiv 2021 · DOI · arXiv

TL;DR

This paper explores "weak degeneracy," a flexible new tool in graph theory, to prove that specific classes of planar and toroidal graphs are easier to color than previously thought. By identifying key reducible structures, the authors improve the bounds for several complex coloring parameters, including DP-paint number and list vertex arboricity, for graphs with restricted cycle configurations.

What Problem Does This Paper Address?

In graph theory, "coloring" isn't just about maps; it’s a fundamental way to handle scheduling, resource allocation, and network design. A central challenge is determining the minimum number of colors needed for a graph. One way to estimate this is through degeneracy—think of it as a measure of how "sparse" or "thin" a graph is. If you can always find a vertex with few neighbors and "peel" it away like an onion, the graph has low degeneracy and is easy to color.

However, standard degeneracy is sometimes too rigid. Recently, researchers Bernshteyn and Lee introduced weak degeneracy, which allows for more complex "peeling" operations. This paper applies this new framework to three specific, difficult-to-analyze graph families:

  1. Planar graphs avoiding certain small configurations.
  2. Toroidal graphs (graphs drawn on a donut shape) avoiding specific structures.
  3. Planar graphs where 5-cycles (pentagons) do not share vertices.

The goal is to prove these graphs have a "strictly $f$-degenerate transversal," a powerful property that simultaneously solves several advanced coloring problems (List coloring, Forested coloring, and DP-coloring).

Methods

The authors employ Structural Graph Theory combined with the Discharging Method.

  • Reducible Configurations: The authors identify small subgraphs (configurations) that are "reducible." If a graph contains one of these, you can technically remove it, color the rest of the graph by induction, and then successfully extend that coloring back to the removed part.
  • Discharging Method: To prove that every graph in their target classes contains at least one reducible configuration, they use a "discharging" argument. They assign an initial "charge" to vertices and faces based on their degrees and then redistribute that charge according to specific rules. If the final charge distribution leads to a contradiction (e.g., a total positive charge when the sum must be zero), it proves that a reducible structure must exist.
  • Weak Degeneracy Operations: They specifically utilize the DeleteSave operation, which allows them to remove a vertex while "saving" a color constraint for a neighbor, providing more flexibility than standard vertex removal.

Datasets

As a theoretical mathematics paper, no external datasets were used. The "data" consists of the mathematical properties of abstract graph classes defined by their embedding (planar or toroidal) and forbidden subgraphs.

Key Insights and Ideas

  • The Unified Approach: The most significant insight is using the "strictly $f$-degenerate transversal" as a master key. Instead of proving bounds for list coloring and DP-coloring separately, the authors prove this one property, which automatically yields results for multiple coloring variants.
  • Weak vs. Ordinary Degeneracy: The paper demonstrates that weak degeneracy is a much more potent tool for planar graphs with restricted cycles. It allows the authors to handle "bad" cycles (like certain 4-cycles) that would normally break standard degeneracy proofs.
  • Cycle Constraints: The authors show that forbidding "intersecting 5-cycles" is a powerful enough constraint to significantly lower the complexity of a planar graph, bringing its Alon-Tarsi number down to four.

Key Results

The paper provides significantly improved bounds for three classes of graphs:

  • Weakly 3-degenerate: All three studied classes are proven to be weakly 3-degenerate.
  • DP-paint number $\le 4$: This is a major improvement over previous results that often capped at 5 or higher.
  • List vertex arboricity $\le 2$: This means the vertices of these graphs can be partitioned into just two sets, each of which forms a forest (a graph with no cycles).
  • Alon-Tarsi number $\le 4$: Proven for the planar graph classes (the first and third classes), providing a bound for a particularly restrictive algebraic coloring parameter.
  • Efficiency: These results "greatly improve" upon a wide range of previous findings in the literature (citing over 10 prior papers) by providing tighter bounds using a more generalized framework.

Limitations and Future Work

The authors note that their results for toroidal graphs cannot be easily strengthened. Specifically, they point out that for any integer $k \ge 6$, there are toroidal graphs without certain cycle lengths that still require five colors, meaning the "planar-to-toroidal" jump has inherent limits.

Future work could involve:

  • Exploring whether these weak degeneracy techniques can be applied to graphs with even fewer restrictions (e.g., allowing some intersecting cycles).
  • Investigating the gap between weak degeneracy and the Alon-Tarsi number for toroidal embeddings, which remains less understood than the planar case.

Summary updated

Abstract

Bernshteyn and Lee defined a new notion, weak degeneracy, which is slightly weaker than the ordinary degeneracy. It is proved that strictly $f$-degenerate transversal is a common generalization of list coloring, $L$-forested-coloring and DP-coloring. In this paper, we consider three classes of graphs, including planar graphs without any configuration in Fig. 2, toroidal graphs without any configuration in Fig. 5, and planar graphs without intersecting $5$-cycles. We give structural results for each class of graphs, and prove each structure is reducible for weakly $3$-degenerate and the existence of strictly $f$-degenerate transversals. As consequences, these three classes of graphs are weakly $3$-degenerate, and have a strictly $f$-degenerate transversal. Then these three classes of graph have DP-paint number at most four, and have list vertex arboricity at most two. This greatly improve all the results in [2-4, 11-13, 16-18, 22, 25, 32, 34]. Furthermore, the first and the third classes of graphs have Alon-Tarsi number at most four.
BibTeX
@misc{wang2021variable,
  author = {Qianqian Wang and Tao Wang and Xiaojing Yang},
  title = {{Variable degeneracy of graphs with restricted structures}},
  year = {2021},
  eprint = {2112.09334},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.09334},
}

Loading related content...

Figure