Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs

Mauro Lucci, Graciela Nasini, Paola Tolomei, Luis Miguel Torres

arXivarxiv/2610.09154Oct 6, 2026math.COscore 0

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.…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.09154
curl -X POST /api/v1/records/arxiv/2610.09154/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.09154/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'