List Packing and Correspondence Packing of Planar Graphs

Basic Information

• Paper ID: 2401.01332
• Title: List Packing and Correspondence Packing of Planar Graphs
• Authors: Daniel W. Cranston (Virginia Commonwealth University), Evelyne Smith-Roberge (Georgia Tech)
• Classification: math.CO (Combinatorics)
• Publication Date: December 6, 2024 (arXiv version 3)
• Paper Link: https://arxiv.org/abs/2401.01332

Abstract

This paper investigates list packing and correspondence packing problems for planar graphs. For a graph $G$ and list assignment $L$ where $|L(v)|=k$ for all vertices $v$, an $L$-packing consists of $L$-colorings $\phi_1,\cdots,\phi_k$ such that $\phi_i(v)\neq\phi_j(v)$ for all $v$ and distinct $i,j\in\{1,\ldots,k\}$. Let $\chi^{\star}_{\ell}(G)$ denote the minimum $k$ such that $G$ admits an $L$-packing for every list assignment $L$ with $|L(v)|=k$. The paper proves that: (i) $\chi^{\star}_{\ell}(G)\leq 8$ for all planar graphs $G$ with girth at least 3; (ii) $\chi^{\star}_{\ell}(G)\leq 5$ for all planar graphs $G$ with girth at least 4; (iii) $\chi^{\star}_{\ell}(G)\leq 4$ for all planar graphs $G$ with girth at least 5. These results also hold for the analogous parameter $\chi^{\star}_c$ for correspondence coloring.

Research Background and Motivation

1. Core Problem: Investigating upper bounds on the list packing number and correspondence packing number for planar graphs. List packing generalizes list coloring by requiring multiple disjoint list colorings.
2. Problem Significance:
   • List coloring is a classical problem in graph theory with extensive theoretical and practical applications
   • Packing problems are natural generalizations of coloring problems, addressing optimization in resource allocation
   • Planar graphs, as an important graph class, possess special theoretical significance in coloring properties
3. Existing Limitations:
   • Cambie et al. (2024) proved $\chi^{\star}_c(G)\leq 10$ for all planar graphs $G$
   • This bound is relatively coarse and requires further refinement
   • Lack of fine-grained analysis for planar graphs with different girths
4. Research Motivation:
   • Improve known upper bounds, particularly addressing questions raised by Cambie et al.
   • Establish precise relationships between girth and packing numbers
   • Provide a unified analytical framework for correspondence coloring

Core Contributions

1. Significantly improved upper bounds on packing numbers for planar graphs: Refined $\chi^{\star}_c(G)\leq 10$ to $\chi^{\star}_c(G)\leq 8$
2. Established precise relationships between girth and packing numbers:
   • Girth ≥ 4: $\chi^{\star}_c(G)\leq 5$
   • Girth ≥ 5: $\chi^{\star}_c(G)\leq 4$ (optimal)
3. Provided completely hand-verifiable proofs: Unlike concurrent work, avoided computer verification
4. Unified treatment of list packing and correspondence packing: All results apply to both packing types
5. Demonstrated optimality for girth ≥ 5 case: Constructed examples showing the bound is tight

Methodology Details

Task Definition

List Packing: Given a graph $G$ and $k$-assignment $L$ (each vertex $v$ has $|L(v)|=k$ available colors), find $k$ $L$-colorings $\phi_1,\ldots,\phi_k$ such that:

1. Each $\phi_i$ is a valid $L$-coloring
2. For any vertex $v$ and distinct $i,j$, we have $\phi_i(v)\neq\phi_j(v)$

Correspondence Packing: Defined similarly, but using correspondence colorings instead of list colorings, with stronger constraints.

Core Technical Framework

1. Auxiliary Bipartite Graph Method

• Definition: For vertex $v$ and existing packing $\phi$, construct auxiliary bipartite graph $H_v$
• Part A: Represents $k$ colors
• Part B: Represents $k$ colorings $\phi_1,\ldots,\phi_k$
• Edges: $i\phi_j \in E(H)$ if and only if we can set $\phi_j(v)=i$

2. Application of Hall's Theorem

Utilize Hall's theorem to determine if a bipartite graph admits a perfect matching:

• Obstruction: Set $X \subseteq A$ satisfying $|N(X)| < |X|$
• Key Observation: Size of obstructions in $(s,t)$-bipartite graphs is constrained

3. Structural Analysis Tools

Proposition 5: If $G$ is an $(s,t)$-bipartite graph and there exists $X \subseteq A$ with $|X| > |N(X)|$, then $t+1 \leq |X| \leq s-t$.

Corollary 6: If $\chi^{\star}_c(G-v) \leq k$ and $d(v) \leq k/2$, then $\chi^{\star}_c(G) \leq k$.

Main Proof Strategies

1. Girth ≥ 4 Case (Theorem 12)

• Discharging Method: Assign initial charge to each vertex equal to its degree
• Discharging Rules: Each degree-3 vertex receives $1/3$ charge from each neighbor
• Forbidden Configurations:
  • Degree-3 vertices cannot be adjacent
  • No edge $vw$ exists where $d(v)=3$ and $d(w) \leq 4$
  • Degree-5 vertices are adjacent to at most three degree-3 vertices

2. Girth ≥ 5 Case (Theorem 15)

Employs more refined analysis:

• Key Lemma: Each vertex in a $(4,2)$-bipartite graph is incident to at least two edges contained in a 1-factor
• Path Analysis: Focuses on paths $xvy$ formed by degree-3 vertices
• Repacking Technique: Modifies colorings of neighboring vertices to create expansion space for target vertex

3. General Planar Graphs Case (Theorem 19)

• Borodin's Structural Theorem: Planar graphs with $\delta(G) \geq 5$ contain a triangle $uvw$ with $d(u)+d(v)+d(w) \leq 17$
• Obstruction Type Analysis: Defines 4 types of obstructions and handles each separately
• Complex Repacking: May require simultaneous modification of colorings for two vertices

Experimental Setup

This is a purely theoretical paper with no experimental verification. All results are obtained through rigorous mathematical proofs.

Core Technical Innovations

1. Systematic Obstruction Classification

Defines 4 types of obstructions in $(8,3)$-bipartite graphs:

• Type 1: $|X|=5$, $|N(X)|=3$
• Type 2: $|X|=4$, $|N(X)|=3$, with specific extension structure
• Type 3: Similar to Type 2 but with different extension structure
• Type 4: $|X|=4$, $|N(X)|=3$ cases not in previous types

2. Unified Analytical Framework

Establishes equivalence between list coloring and correspondence coloring through Lemma 8, allowing "straightening" of arrangements on tree structures.

3. Precise Degree Constraints

Utilizes Euler's formula to establish relationships between girth and average degree:

• Planar graphs with girth $g$ have maximum average degree $< 2g/(g-2)$
• Girth 4: average degree $< 4$
• Girth 5: average degree $< 10/3$

Main Results

Theorem Statements

1. Theorem 1: $\chi^{\star}_c(G) \leq 8$ for all planar graphs $G$
2. Theorem 2: $\chi^{\star}_c(G) \leq 5$ for all planar graphs $G$ with girth ≥ 4
3. Theorem 3: $\chi^{\star}_c(G) \leq 4$ for all planar graphs $G$ with girth ≥ 5, and this bound is optimal

Optimality

Demonstrated through examples using cycles $C_k$ ($k \geq 3$):

• $\chi^{\star}_\ell(C_k) = 3 < 4 = \chi^{\star}_c(C_k)$
• Shows correspondence packing is more difficult than list packing
• The bound 4 for girth ≥ 5 is tight

Related Work

1. Cambie et al. (2024): First systematic study of packing problems, proving $\chi^{\star}_c(G) \leq 10$
2. Concurrent Work: Independent work by Cambie, Cames van Batenburg, and Zhu proving identical results but relying on computer verification
3. Classical Coloring Theory: Built on foundational work by Heawood, Ringel-Youngs and others on surface graph coloring
4. Correspondence Coloring: Theoretical framework established by Dvořák-Postle et al.

Conclusions and Discussion

Main Conclusions

1. Significantly improved upper bounds on packing numbers for planar graphs
2. Established precise relationships between girth and packing numbers
3. Provided completely constructive proof methods
4. Unified treatment of list packing and correspondence packing

Limitations

1. Proofs are highly technical, involving extensive case analysis
2. Problems for graphs on general surfaces remain unresolved
3. Optimality of certain bounds remains incompletely determined

Future Directions

The paper proposes 6 open problems:

1. Determine exact values of $\chi^{\star}_\ell(\mathcal{P}_3)$ and $\chi^{\star}_\ell(\mathcal{P}_4)$
2. Study packing numbers for graph classes with bounded maximum average degree
3. Packing numbers for planar bipartite graphs
4. Packing numbers for graphs on general surfaces
5. Relationships with Heawood numbers
6. Packing numbers for graphs without complete subgraphs

In-Depth Evaluation

Strengths

1. Significant Theoretical Contribution: Substantially improves bounds on important problems
2. Methodological Innovation: Obstruction classification and unified analytical framework have universal significance
3. Complete Proofs: Avoids computer verification; all proofs are hand-verifiable
4. Optimal Results: Achieves optimal bounds for girth ≥ 5 case
5. Clear Exposition: Technical details well-organized; examples aid understanding

Weaknesses

1. Complex Proofs: Extensive technical details and case analysis
2. Generalizability: Applicability of methods to other graph classes unclear
3. Computational Complexity: Algorithmic complexity not discussed

Impact

1. Theoretical Value: Advances development of graph coloring theory
2. Methodological Value: Technical tools potentially applicable to other problems
3. Open Problems: Proposed questions provide direction for future research

Application Scenarios

1. Conflict avoidance in resource allocation
2. Spectrum allocation and network coloring
3. Constraint satisfaction in scheduling problems
4. Packing problems in combinatorial optimization

References

The paper cites 20 important references, including:

• Borodin's classical results on planar graph structure
• Cambie et al.'s pioneering work on packing problems
• Dvořák-Postle's theory on correspondence coloring
• Heawood's classical theory on surface graph coloring

This paper makes important contributions to combinatorics, particularly in graph coloring theory. Through sophisticated technical methods, it significantly improves bounds on planar graph packing problems, laying a solid foundation for further development in this field.