A Planar Linear Arboricity Conjecture

Marek Cygan, Lukasz Kowalik, Borut LuzarCIAC 2010 · DOI

TL;DR

This paper tackles the problem of "linear arboricity" for planar graphs, which is about efficiently partitioning a graph's edges into paths. The authors prove a significant part of a conjecture stating that for planar graphs with maximum degree $\Delta \ge 9$, the linear arboricity is $\lceil \Delta/2 \rceil$. They also provide an efficient algorithm to achieve this coloring.

What Problem Does This Paper Address?

The core problem is determining the linear arboricity of a graph, denoted as $la(G)$. This is the minimum number of linear forests (collections of paths) needed to cover all edges of a graph $G$. A fundamental conjecture, known as the Linear Arboricity Conjecture (LAC), states that for any simple graph with maximum degree $\Delta$, its linear arboricity is either $\lceil \Delta/2 \rceil$ or $\lceil \Delta/2 \rceil + 1$. While this conjecture is still open in general, it has been proven for planar graphs.

However, a stronger conjecture exists specifically for planar graphs: for any planar graph with maximum degree $\Delta \ge 6$, its linear arboricity is exactly $\lceil \Delta/2 \rceil$. This paper focuses on proving a significant portion of this planar graph conjecture. Specifically, it aims to show that for planar graphs with maximum degree $\Delta \ge 9$, the linear arboricity is indeed $\lceil \Delta/2 \rceil$. This is important because it provides a tighter bound and a more precise understanding of how efficiently planar graphs can be decomposed into paths, which has implications for graph coloring and other structural properties.

Methods

The paper employs a combination of combinatorial techniques and algorithmic design. The proof of the main theorem relies heavily on the discharging method, a powerful tool in graph theory often used in conjunction with the Four Color Theorem. This method involves:

  1. Assigning initial charges: Each vertex and face of a planar graph is assigned an initial charge based on its degree or length.
  2. Defining discharging rules: These rules specify how charge is transferred between vertices and faces based on their degrees and adjacencies. The goal is to redistribute charge such that all elements end up with a non-negative charge.
  3. Proving minimality and structural properties: Before applying the discharging method, the authors establish crucial structural properties of minimal counterexamples (graphs that violate the conjecture). This involves proving several lemmas that characterize forbidden subgraphs or configurations. These lemmas are essential for ensuring that the discharging rules can be applied effectively and that the redistribution of charge leads to the desired outcome.

For the algorithmic part, the authors adapt techniques from existing linear-time algorithms for edge-coloring planar graphs. They develop an algorithm that finds a linear coloring using a bounded number of colors. This algorithm relies on identifying and processing "reducible configurations" (forbidden subgraphs) in linear time. The algorithm uses queues to manage these configurations and a recursive procedure to color the graph.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Planar graphs are "easier" for linear arboricity: The paper reinforces the idea that planarity significantly constrains graph structure, allowing for tighter bounds on linear arboricity compared to general graphs.
  • The discharging method is powerful for planar graph problems: The successful application of the discharging method to prove the $\Delta \ge 9$ case highlights its effectiveness in handling problems related to planar graph coloring and decomposition.
  • Structural lemmas are crucial: The series of lemmas characterizing forbidden subgraphs (e.g., Lemma 4, Lemma 5, Lemma 6, etc.) are critical. They systematically eliminate problematic configurations, simplifying the problem and paving the way for the discharging method.
  • Algorithmic construction mirrors proof: The algorithm developed to find the linear coloring is directly inspired by the proof of the main theorem, demonstrating a strong connection between theoretical results and practical algorithms.
  • The $\Delta \ge 9$ threshold is key: The paper focuses on proving the result for $\Delta \ge 9$, leaving open the cases $\Delta = 6, 8$ for planar graphs. This suggests that these lower $\Delta$ values might require different techniques or exhibit different behaviors.

Key Results

  • Theorem 1: For every planar graph $G$ with maximum degree $\Delta(G) \ge 9$, the linear arboricity $la(G) = \lceil \Delta(G)/2 \rceil$. This is a significant step towards proving the conjecture for all planar graphs.
  • Proposition 3: Any simple planar graph of maximum degree $\Delta$ has a linear coloring in $\max\{\lceil \Delta/2 \rceil, 5\}$ colors. This is a more general result that is proven using the discharging method and serves as a basis for Theorem 1.
  • Algorithm: An $O(n \log n)$ algorithm is presented that partitions the edges of a planar graph into $\max\{la(G), 5\}$ linear forests. This algorithm is efficient and optimal for $\Delta \ge 9$.

Limitations and Future Work

  • Open cases for planar graphs: The paper explicitly leaves open the cases for planar graphs with maximum degree $\Delta = 6$ and $\Delta = 8$ for the conjecture $la(G) = \lceil \Delta/2 \rceil$. Proving these cases would complete the planar graph conjecture.
  • NP-completeness for $\Delta=4$: The paper conjectures that determining if a planar graph with maximum degree 4 has linear arboricity 2 is NP-complete. This suggests that for small maximum degrees, the problem might be computationally hard.
  • General graphs: While the paper focuses on planar graphs, the general Linear Arboricity Conjecture for all graphs remains open. The techniques used here are specific to planar graphs and may not directly apply to general graphs.
  • Algorithm for $\Delta < 10$: The paper presents an algorithm for $\Delta < 10$ that finds a coloring in $\max\{\lceil \Delta/2 \rceil, 5\}$ colors. While efficient, it's noted that for $\Delta \ge 9$, the bound $\lceil \Delta/2 \rceil$ is achieved. Further work could explore if the $\max\{\lceil \Delta/2 \rceil, 5\}$ bound can be tightened for specific small $\Delta$ values in the planar case.

Summary updated

BibTeX
@inproceedings{cygan2010planar,
  author = {Marek Cygan and Lukasz Kowalik and Borut Luzar},
  title = {{A Planar Linear Arboricity Conjecture}},
  booktitle = {CIAC},
  year = {2010},
  doi = {10.1007/978-3-642-13073-1\_19},
}
Figure