Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs
Abstract
The Double-Partition Coloring Problem (DPCP) is a recently introduced generalization of several coloring problems on graphs and hypergraphs, including the Partition Coloring Problem, the List Coloring Problem, and the Conflict-Free Coloring Problem (CFCP). In this work, we further investigate the structural and computational properties of the DPCP and develop exact and heuristic solution approaches. We derive structural results that allow the detection of infeasible instances and the reduction of their size. We propose one-step and two-step heuristics for obtaining high-quality solutions. These procedures are incorporated into an enhanced branch-and-price algorithm based on a set covering formulation of the DPCP. The algorithm further includes new strategies for solving the NP-hard pricing problem. Computational experiments show that the proposed branch-and-price algorithm and a compact integer programming formulation complement each other: while the compact formulation is generally more effective on sparse instances, branch-and-price performs particularly well on denser and larger instances. In particular, these are the first exact algorithms to be computationally evaluated on various CFCP instances.
Related
- List coloring uncrowded hypergraphs at the shattering threshold
- Proper Conflict-Free Coloring on Structured Graph Classes: Bounds, Exact Algorithms, and Hardness
- Bounds for B-coloring planar and outerplanar graphs
- Edge‐Coloring a Graph G so That Every Copy of a Graph H Has an Odd Color Class
- FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
BibTeX
@misc{lucci2026doublepartition,
title = {{Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs}},
author = {Mauro Lucci and Graciela Nasini and Paola Tolomei and Luis Miguel Torres},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09154},
eprint = {2610.09154},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09154},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs
AU - Mauro Lucci
AU - Graciela Nasini
AU - Paola Tolomei
AU - Luis Miguel Torres
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.09154
UR - https://arxiv.org/abs/2610.09154
AB - The Double-Partition Coloring Problem (DPCP) is a recently introduced generalization of several coloring problems on graphs and hypergraphs, including the Partition Coloring Problem, the List Coloring Problem, and the Conflict-Free Coloring Problem (CFCP). In this work, we further investigate the structural and computational properties of the DPCP and develop exact and heuristic solution approaches. We derive structural results that allow the detection of infeasible instances and the reduction of their size. We propose one-step and two-step heuristics for obtaining high-quality solutions. These procedures are incorporated into an enhanced branch-and-price algorithm based on a set covering formulation of the DPCP. The algorithm further includes new strategies for solving the NP-hard pricing problem. Computational experiments show that the proposed branch-and-price algorithm and a compact integer programming formulation complement each other: while the compact formulation is generally more effective on sparse instances, branch-and-price performs particularly well on denser and larger instances. In particular, these are the first exact algorithms to be computationally evaluated on various CFCP instances.
ER -