Packing six T-joins in plane graphs

Zdenĕk Dvořák, Ken‐ichi Kawarabayashi, Daniel Král͏̌

Abstract

In the study of graph theory, the packing of edge-disjoint $T$-joins is a central problem with deep connections to the Four Color Theorem. This paper settles the $k=6$ case of a long-standing conjecture regarding plane graphs. By reducing the problem to a 6-edge-coloring challenge for 6-regular plane multigraphs and employing the discharging method, the authors demonstrate that if all $T$-cuts of a plane graph $G$ have the same parity and a minimum size of at least six, then $G$ contains six edge-disjoint $T$-joins.

Introduction

A $T$-join in a graph $G$ is a subgraph where a specific even subset of vertices $T$ has odd degrees, while all other vertices have even degrees. Conversely, a $T$-cut is a partition of the graph's vertices such that an odd number of vertices from $T$ are on one side. A fundamental conjecture in this field states that if every $T$-cut in a plane graph has the same parity and a minimum size of $k$, then the graph contains $k$ edge-disjoint $T$-joins.

This conjecture is not merely an abstract exercise; it is deeply rooted in the history of graph theory. The case where $k=3$ is equivalent to the Four Color Theorem. Previous milestones include proofs for $k=4$ and $k=5$ by Guenin. This research addresses the next open case, $k=6$, providing a critical step toward a general proof for all $k$.

Methodology

The authors utilize a proof by contradiction, focusing on the properties of a minimal counterexample. If a graph exists that satisfies the $T$-cut conditions but fails to allow for six disjoint $T$-joins, it must possess specific structural properties that the authors prove are impossible.

Reduction to Edge-Coloring

The proof begins by showing that for $k=6$, the problem is equivalent to a coloring problem. Specifically, the authors prove that any 6-regular plane multigraph (where every vertex has degree 6) with no odd cuts smaller than six must be 6-edge-colorable. This reduction simplifies the search for $T$-joins into a search for a valid edge coloring.

The Discharging Method

To analyze the structural constraints of the graph, the researchers employ the discharging method, the same technique famously used to prove the Four Color Theorem. The process follows these steps:

  1. Initial Charging: Based on Euler’s formula, an "initial charge" is assigned to the faces and multigons (sequences of multiple edges between vertices) of the graph. For a 6-regular plane graph, the total charge is exactly -6.
  2. Discharging Rules: The authors define a meticulous set of rules to redistribute this charge. Charge is moved from larger faces to smaller ones or to specific types of multigons (such as bigons or trigons).
  3. Contradiction: The goal is to show that after the redistribution, every component of the graph (every face and multigon) ends up with a non-negative charge. Since the total charge of the graph must remain -6, but the discharging rules result in every part being $\ge 0$, a counterexample cannot logically exist.

Key Insights and Structural Constraints

The success of the discharging method relies on identifying the local structures of a minimal counterexample. The authors identify several "forbidden" configurations:

  • Parity Constraints: The requirement that all $T$-cuts have the same parity is essential. In a 6-regular graph, this implies every cut must have an even number of edges, which significantly constrains how colors can be distributed around vertices.
  • Multigon Configurations: The paper identifies that a minimal counterexample cannot contain certain arrangements of bigons (two edges between two vertices) or trigons (three edges) without violating the minimum cut-size constraints.
  • Refined Rules: The researchers developed specific values for charge transfer (e.g., Rule RQ providing 1.5 units of charge) to ensure that "dangerous" configurations—such as 5-faces adjacent to specific trigons—receive exactly enough charge to reach a non-negative state.

Results

The primary contribution of this work is Theorem 1: If $G$ is a plane multigraph and $T$ is an even subset of its vertices where every $T$-cut has the same parity and size at least six, then $G$ contains six edge-disjoint $T$-joins.

This is established through Theorem 2, which confirms the 6-edge-colorability of 6-regular plane multigraphs with no odd cuts smaller than six. This result effectively closes the $k=6$ chapter of the conjecture.

Conclusion and Future Work

While this paper settles the $k=6$ case, the general conjecture for arbitrary $k$ remains one of the most significant open problems in the field. Concurrent work by other researchers (such as Chudnovsky et al.) has addressed cases for $k=7$ and $k=8$, indicating that while the discharging method is robust, the complexity of the rules and configurations grows exponentially with $k$.

The ultimate objective remains a unified proof for all $k$, or a proof of the broader Seymour’s Conjecture, which seeks to extend these results to all graphs that do not contain a Petersen minor, moving beyond the constraint of planarity.

Summary updated

Abstract

Let G be a plane graph and T an even subset of its vertices. It has been conjectured that if all T-cuts of G have the same parity and the size of every T-cut is at least k, then G contains k edge-disjoint T-joins. The case k=3 is equivalent to the Four Color Theorem, and the cases k=4, which was conjectured by Seymour, and k=5 were proved by Guenin. We settle the next open case k=6.
BibTeX
@article{dvorak2016packing,
  author = {Zdenĕk Dvořák and Ken‐ichi Kawarabayashi and Daniel Král͏̌},
  title = {{Packing six T-joins in plane graphs}},
  journal = {J. Comb. Theory B},
  year = {2016},
  doi = {10.1016/j.jctb.2015.09.002},
}
Figure