Odd list-coloring of graphs of small Euler genus with no short cycles of specific types

Basic Information

• Paper ID: 2508.15255
• Title: Odd list-coloring of graphs of small Euler genus with no short cycles of specific types
• Authors: Rishi Balaji, Victoria Khazhinsky, Chun-Hung Liu, Kevin Qin
• Classification: math.CO (Combinatorics)
• Publication Date: October 14, 2025
• Paper Link: https://arxiv.org/abs/2508.15255

Abstract

This paper investigates the list-coloring version of odd coloring for graphs. The main result establishes that if a graph G can be embedded on a torus or Klein bottle, contains no cycles of length 3, 4, or 6, and has no two 5-cycles sharing an edge, then for every function L assigning a color set of size 5 to each vertex, there exists a proper coloring such that some color appears an odd number of times in the neighborhood of each non-isolated vertex. In particular, every graph embeddable on a torus or Klein bottle with no cycles of length 3, 4, 6, or 8 is odd 5-choosable. The results demonstrate that the number of colors in these theorems is optimal.

Research Background and Motivation

Problem Definition

1. Odd coloring problem: Odd coloring is a variant of proper coloring requiring that for each non-isolated vertex, at least one color appears an odd number of times in its neighborhood
2. List coloring: Each vertex has an associated list of available colors, and the coloring must select colors from respective lists
3. Surface-embedded graphs: Investigation of coloring properties for graphs embeddable on specific surfaces (torus, Klein bottle)

Research Significance

• Although the concept of odd coloring is relatively recent (introduced by Petruševski and Škrekovski in 2022), it has attracted considerable attention
• Combines two important concepts in graph theory: surface embedding and restricted cycle structure
• Provides important insights into understanding graph coloring theory under topological constraints

Limitations of Existing Research

• Petruševski and Škrekovski conjectured that every planar graph is odd 5-colorable, but the best current result is odd 8-colorable
• Fewer known results exist for graphs on more general surfaces
• Research on the list-coloring version of odd coloring is even scarcer

Core Contributions

1. Main Theorem: Proves that graphs embeddable on a torus or Klein bottle satisfying specific cycle conditions are odd 5-choosable
2. Optimality Results: Demonstrates that the required number of colors (5) is optimal, with counterexamples requiring 6 or 7 colors
3. Technical Framework: Develops stronger technical results (Theorem 1.3 as a generalization of Theorem 1.1)
4. Methodological Innovation: Employs the discharging method to systematically analyze graph structure

Detailed Methodology

Task Definition

Input: Graph G embeddable on a torus or Klein bottle satisfying cycle length restrictions, and a 5-list assignment L Output: A proper L-coloring such that some color appears an odd number of times in the neighborhood of each non-isolated vertex Constraints:

• No cycles of length 3, 4, or 6
• No two 5-cycles sharing an edge

Core Technical Methods

R-length Concept

For a graph G and edge set R ⊆ E(G), the R-length of a cycle C is defined as |E(C)| + |E(C) ∩ R|. This concept unifies the treatment of the original problem and its generalizations.

R-relaxed Vertices

A vertex v is R-relaxed if:

• deg(v) is odd or 0, or
• v is adjacent to some edge in R

Main Technical Theorem (Theorem 1.3)

Let G be embeddable on a torus or Klein bottle, and R ⊆ E(G). If:

• There are no cycles of R-length 3, 4, or 6
• No two cycles of R-length 5 share exactly one edge

Then for every 5-list assignment L, there exists a proper L-coloring such that some color appears an odd number of times in the neighborhood of each non-R-relaxed vertex.

Proof Strategy

Minimal Counterexample Analysis

Assuming a minimal counterexample G exists, the proof analyzes its structural properties:

1. Connectivity: Proves G must be connected (Lemma 3.1)
2. Minimum Degree: Every vertex has degree at least 3 (Lemma 3.2)
3. 3-vertex Restrictions: 3-degree vertices cannot be adjacent to too many R-relaxed vertices (Lemma 3.3)
4. Cycle Structure: Detailed analysis of R-lengths and mutual relationships of 3-cycles, 4-cycles, and 5-cycles

Discharging Method

Employs the classical discharging technique:

Initial Charge:

• Vertex v: ch(v) = deg(v) - 4
• Face f: ch(f) = len(f) - 4

Discharging Rules (R1)-(R8):

• (R1): (≥5)-faces send 1/2 units of charge to adjacent 3-vertices
• (R2)-(R6): Handle charge transfers between faces
• (R7): (≥5)-vertices send 1/2 units of charge to adjacent 5-faces
• (R8): (≥6)-vertices send 1/3 units of charge to qualifying 5-faces

Charge Analysis

Through meticulous charge calculations, the proof establishes:

• Final charge of each vertex and face is non-negative
• Total charge is strictly positive
• This contradicts Euler's formula, thereby refuting the existence of a counterexample

Experimental Setup

Theoretical Verification

This is purely theoretical work, with results verified primarily through mathematical proof:

1. Constructive Proof: For graphs satisfying the conditions, constructively provides odd 5-colorings
2. Counterexample Construction: Proves optimality of the color number 5
   • 5-cycles are not odd 4-choosable
   • 1-subdivisions of K₇ are not odd 6-choosable
   • 1-subdivisions of K₆ are not odd 5-choosable

Technical Tools

• Euler's formula for constraints on graphs on surfaces
• Systematic application of the discharging method
• Local analysis techniques for graph structure

Experimental Results

Main Results

Theorem 1.1 (Main Theorem)

A graph G embeddable on a torus or Klein bottle with no cycles of length 3, 4, or 6 and no two 5-cycles sharing an edge is odd 5-choosable.

Corollary 1.2

A graph G embeddable on a torus or Klein bottle with no cycles of length 3, 4, 6, or 8 is odd 5-choosable.

Optimality

• The color number 5 is optimal: 5-cycles require 5 colors
• Cycle length restrictions are necessary: counterexamples of girth 6 exist requiring 6-7 colors

Technical Results Verification

Key lemmas are proven through detailed structural analysis:

• Lemma 3.5: 3-cycles must have R-length 5, with all vertices being R-relaxed
• Lemma 3.16: 4-vertices cannot be adjacent only to 4-faces
• Lemma 4.11: Total charge after discharging is strictly positive

Related Work

Development of Odd Coloring Research

1. Origins: Petruševski and Škrekovski (2022) introduced the concept and conjectured that planar graphs are odd 5-colorable
2. Planar Graph Results:
   • Initial proof: odd 9-colorable
   • Improvement: Petr and Portier proved odd 8-colorable
3. Surface Generalizations: Metrebian and Tian and Yin proved toroidal graphs are odd 9-colorable

List Coloring Background

• List coloring is an important branch of coloring theory
• This paper is the first to systematically study the list-coloring version of odd coloring
• Combining surface embedding with cycle structure constraints represents a new research direction

Methodological Contributions

• Application of the discharging method to odd coloring
• Introduction of the R-length concept unifying treatment of different cases
• Provides a technical framework for subsequent research

Conclusions and Discussion

Main Conclusions

1. Under appropriate cycle structure constraints, graphs on tori and Klein bottles exhibit favorable odd list-coloring properties
2. Five colors suffice for such graphs, and this bound is tight
3. The discharging method is an effective tool for analyzing such problems

Limitations

1. Surface Restrictions: Results apply only to surfaces with Euler genus at most 2
2. Cycle Conditions: Multiple short cycles must be excluded, making conditions quite restrictive
3. Existential Nature: The proof is existential without providing efficient algorithms

Future Directions

1. Generalization to surfaces of higher genus
2. Relaxation of cycle length restrictions
3. Investigation of algorithmic complexity and concrete construction methods
4. Exploration of odd list-coloring properties for other graph classes

In-Depth Evaluation

Strengths

Technical Innovation

1. Conceptual Innovation: Introduction of R-length and R-relaxed concepts elegantly unifies different variants of the problem
2. Rigorous Methodology: Application of the discharging method is systematic and complete
3. Optimal Results: Proves optimality of the color number, yielding tight results

Theoretical Contributions

1. Novel Results: Significant progress in the emerging field of odd list-coloring
2. Technical Framework: Provides methodology that can be adapted for subsequent research
3. Completeness: Handles both main results and technical details comprehensively

Academic Value

1. Important Problem: Connects graph coloring, topological graph theory, and combinatorial optimization
2. Deep Results: Reveals the impact of surface constraints on coloring properties
3. General Techniques: Methods potentially applicable to other related problems

Weaknesses

Technical Limitations

1. Restrictive Conditions: Requirements on cycle structure are quite complex, potentially limiting practical applications
2. Surface Limitations: Addresses only the simplest non-trivial surface cases
3. Algorithmic Gap: No concrete algorithm provided for constructing odd colorings

Analytical Depth

1. Parameter Dependence: Insufficient analysis of why exactly 5 colors are necessary
2. Structure Characterization: Limited characterization of structural features of graphs satisfying the conditions
3. Generalization Potential: Further exploration needed for extending techniques to other problems

Impact

Theoretical Impact

• Provides important technical tools and results for the development of odd coloring theory
• May inspire new research directions in surface graph coloring theory
• Novel applications of the discharging method may influence related proof techniques

Practical Value

• Although purely theoretical, may have potential applications in network coloring and spectrum allocation problems
• Provides theoretical foundation for algorithm design

Reproducibility

• Proofs are complete and detailed with clear technical roadmap
• Main results can be independently verified
• Provides solid foundation for subsequent work

Applicable Scenarios

1. Theoretical Research: Graph coloring theory, topological graph theory research
2. Algorithm Design: Network problems requiring special coloring properties
3. Teaching: Classical case study for applications of the discharging method
4. Generalization Research: Extensions to other graph classes or coloring variants

References

The paper cites 38 related references, primarily including:

Foundational Theory:

• Four Color Theorem related work 4,5,6,34
• Surface graph coloring theory 3,18,20,22,33

Odd Coloring Research:

• Concept origins 32
• Planar graph results 31,14,11
• Surface generalizations 29,36

Technical Methods:

• Discharging method applications 25
• Related coloring problems 1,2,10,12,16,17,24,26,27

Overall Assessment: This is a high-quality theoretical paper making important contributions to the emerging field of odd list-coloring. The techniques are rigorous, the results are optimal, and it establishes a solid foundation for the field's development. Although the conditions are technically involved, it opens new research directions with significant academic value.