Disjoint unions and fixed-parameter algorithms for chromatic villainy
Abstract
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 Bw(mG)=mFk(G) whenever k| m, where Fk(G) is the maximum distance to a proper k-coloring over all assignments of k color labels to vertices. Its bounded defect from mFk(G) is eventually periodic; we give an explicit stabilization bound and identify the least period, which divides k. For ordinary villainy, we obtain a computable rational slope Λ(G)≥ Fk(G) such that B(mG)=mΛ(G)+OG(1), where the error is bounded independently of m and eventually periodic, with a computable period and threshold. Consequently the difference between the two values is bounded exactly when Λ(G)=Fk(G), and otherwise grows linearly. The slope is determined by a finite optimization using at most k source assignments. We also answer the unrestricted superadditivity questions negatively: for every C>0, a connected graph can lose more than C in weak villainy after union with a triangle, and some connected $3$-chromatic graph G satisfies B(Gsqcup G)<2B(G)−C. Finally, both exact values on an n-vertex graph can be computed in time f(Bw(G))(n+1)O(1), without either value being supplied. Threshold recognition is fixed-parameter tractable as well.
Related
- Bounds on Treewidth via Excluding Disjoint Unions of Cycles
- Exact and extremal values of chromatic villainy
- Complete characterization of disconnected one-point unions of cycles with local antimagic chromatic number 2
- Code uniqueness of 4-cell connected disjoint clusters in spatial chromatic model
- Parameter estimation in Conditional Sequential Monte Carlo algorithms through Particle Learning
BibTeX
@misc{jiang2026disjoint,
title = {{Disjoint unions and fixed-parameter algorithms for chromatic villainy}},
author = {Jiang Jiang and Yuhan Jiang and Yiyang Li and Lujia Wang and Aitao Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13556},
eprint = {2610.13556},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13556},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Disjoint unions and fixed-parameter algorithms for chromatic villainy
AU - Jiang Jiang
AU - Yuhan Jiang
AU - Yiyang Li
AU - Lujia Wang
AU - Aitao Zhang
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13556
UR - https://arxiv.org/abs/2610.13556
AB - 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_w(mG)=mF_k(G) whenever k| m, where F_k(G) is the maximum distance to a proper k-coloring over all assignments of k color labels to vertices. Its bounded defect from mF_k(G) is eventually periodic; we give an explicit stabilization bound and identify the least period, which divides k. For ordinary villainy, we obtain a computable rational slope Λ(G)≥ F_k(G) such that B(mG)=mΛ(G)+O_G(1), where the error is bounded independently of m and eventually periodic, with a computable period and threshold. Consequently the difference between the two values is bounded exactly when Λ(G)=F_k(G), and otherwise grows linearly. The slope is determined by a finite optimization using at most k source assignments. We also answer the unrestricted superadditivity questions negatively: for every C>0, a connected graph can lose more than C in weak villainy after union with a triangle, and some connected $3$-chromatic graph G satisfies B(Gsqcup G)<2B(G)−C. Finally, both exact values on an n-vertex graph can be computed in time f(B_w(G))(n+1)^O(1), without either value being supplied. Threshold recognition is fixed-parameter tractable as well.
ER -