A Planar linear arboricity conjecture

Marek Cygan, Jianfeng Hou, Lukasz Kowalik, Borut Luzar, Jian-Liang WuJ. Graph Theory 2012 · DOI

Overview

The linear arboricity $la(G)$ of a graph $G$ is the minimum number of linear forests—graphs where every connected component is a path—that partition the edges of $G$. In 1984, Akiyama et al. proposed the Linear Arboricity Conjecture (LAC), stating that for any simple graph of maximum degree $\Delta$, the linear arboricity is either $\lceil \Delta/2 \rceil$ or $\lceil (\Delta + 1)/2 \rceil$. While LAC has been proven to hold for all planar graphs, a specific gap remained regarding the lower bound for even degrees. This paper demonstrates that for planar graphs with even $\Delta \ge 10$, the lower bound $la(G) = \lceil \Delta/2 \rceil$ holds, and provides an efficient algorithm for edge partitioning.

The Linear Arboricity Conjecture in Planar Graphs

The core of the LAC is the relationship between a graph's maximum degree and its decomposability into paths. For general graphs, regular graphs with even degrees require the higher bound $\lceil (\Delta+1)/2 \rceil$. However, planar graphs are inherently sparse due to Euler's formula, which limits their edge density. This sparsity led researchers to conjecture that for planar graphs, the lower bound $\lceil \Delta/2 \rceil$ should be achievable for all $\Delta \ge 6$.

Prior to this work, the conjecture was confirmed for all odd $\Delta$ and for even $\Delta \ge 13$. This paper successfully pushes the boundary for even degrees down to $\Delta = 10$, leaving only the cases of $\Delta = 6$ and $\Delta = 8$ unresolved for planar graphs.

Methodology: Discharging and Reducible Configurations

The authors employ the discharging method, a classic technique in planar graph theory famously used in the proof of the Four Color Theorem. The method involves assigning an initial "charge" to vertices and faces such that the total sum is negative. By defining discharging rules to move these charges, the authors show that any minimal counterexample must contain specific "reducible configurations."

A typical configuration of vertices and edges analyzed during the discharging process.

A configuration is considered reducible if its removal allows the remaining graph to be partitioned into the target number of linear forests, and the configuration itself can then be re-inserted and colored without violating the linear forest constraints (i.e., without creating cycles or exceeding degree limits).

Illustration of a reducible configuration transformation used to extend linear forest partitions.

Algorithmic Contributions

In addition to the theoretical proof, the paper introduces an $O(n \log n)$ algorithm for partitioning a planar graph into $\max\{la(G), 5\}$ linear forests. The algorithm's efficiency is achieved through the use of advanced dynamic data structures, such as Link-Cut trees or Splay trees. These structures enable the algorithm to perform cycle detection in logarithmic time, which is critical for maintaining the path-only requirement of linear forests during the edge assignment process. For graphs with $\Delta \ge 9$, this algorithm is computationally optimal.

Key Results and Future Work

The study concludes that for every planar graph $G$ with maximum degree $\Delta \ge 9$, $la(G) = \lceil \Delta/2 \rceil$. This result settles the conjecture for all cases where $\Delta$ is odd and for even $\Delta \ge 10$.

The paper identifies two primary areas for future research:

  1. The Open Cases: Resolving the conjecture for $\Delta = 6$ and $\Delta = 8$, which require significantly more complex discharging rules.
  2. Complexity Bifurcation: The authors conjecture that while the problem is efficiently solvable for high-degree graphs, determining the linear arboricity for $\Delta = 4$ is likely NP-complete. This suggests a fascinating transition in computational complexity based on the graph's maximum degree.

Summary updated

BibTeX
@article{cygan2012planar,
  author = {Marek Cygan and Jianfeng Hou and Lukasz Kowalik and Borut Luzar and Jian-Liang Wu},
  title = {{A Planar linear arboricity conjecture}},
  journal = {J. Graph Theory},
  year = {2012},
  doi = {10.1002/jgt.20592},
}
Figure