Proper Conflict-Free Coloring on Structured Graph Classes: Bounds, Exact Algorithms, and Hardness
Source: arxiv.org/abs/2611.03906
A proper conflict-free coloring is a proper vertex coloring in which every non-isolated vertex has a neighbor whose color appears exactly once in its open neighborhood. We study this coloring on chordal and ordered bipartite graph classes. For well-partitioned chordal graphs, we prove the tight bound $ω(G)\leq\pcf(G)\leqω(G)+1$ and give an $O(n^2)$ construction from a partition tree. Every assignment of lists of at least $ω(G)+1$ colors also admits a PCF coloring that respects the lists. Deciding whether $ω(G)$ colors suffice is NP-complete, even when the partition tree is a star. This also…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.03906
curl -X POST /api/v1/records/arxiv/2611.03906/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.03906/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'