Disjoint unions and fixed-parameter algorithms for chromatic villainy

Jiang Jiang, Yuhan Jiang, Yiyang Li, Lujia Wang, Aitao Zhang

arXivarxiv/2610.13556Oct 9, 2026math.COscore 0

Chromatic villainy is the maximum, over rearrangements of optimal graph colorings, of the minimum Hamming distance to a proper coloring with the same color multiplicities. Weak villainy allows the repair to change these multiplicities. We give exact composition laws for disjoint unions and determine the eventual growth under repetition. Write $mG$ for the disjoint union of $m$ copies of $G$. For every graph $G$, with $k=χ(G)$, weak villainy satisfies $B_{\mathrm w}(mG)=mF_k(G)$ whenever $k\mid m$, where $F_k(G)$ is the maximum distance to a proper $k$-coloring over all assignments of $k$…

SourceJSON

Comments and reviews

No comments yet.

API

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