Exact and extremal values of chromatic villainy
Abstract
Chromatic villainy measures the largest number of vertices that must change color to repair a rearrangement of an optimal coloring while preserving every color multiplicity. Weak villainy allows different multiplicities in the repair. On the odd cycle C2r+1, we determine the largest repair distance from arbitrary color assignments with a prescribed color-count vector (profile) m to proper colorings with any realizable target profile p: it equals 2r+1−∑Xmin{pX,⌈ mX/2⌉}. In particular, every feasible profile (a,b,c) has ordinary and weak repair radius ⌊ a/2⌋+⌊ b/2⌋+⌊ c/2⌋, and B(C2r+1)=r for r≥2, answering a question of Clark et al. For arbitrary complete multipartite graphs, we give an arithmetic formula for ordinary villainy with at most k2 candidates and an exact finite formula for weak villainy, where k is the number of parts. Both values are fixed-parameter tractable in k for binary-encoded part sizes. We also determine the maximum of each parameter among all n-vertex k-chromatic graphs. For k≥3, the ordinary maximum is min{n,4(n−k)}, except when n=4(n−k)−1 or (n,k)∈{(5,3),(7,3)}, when it is n−1. For k≥2, the weak maximum is n−max{⌈ n/k⌉,2k−n}−ε, where ε∈{0,1} is determined explicitly by n and k. Both extrema are attained by complete multipartite graphs, and a weak extremizer needs at most three distinct part sizes.
Related
- Super-g-Hölder Regularity in Stieltjes Dynamics: Atomic Structure, Exact Extremal Values, and Recovery of the Stieltjes Clock
- Disjoint unions and fixed-parameter algorithms for chromatic villainy
- Exact Values, Extremal Classifications, and Sum-of-Squares Reductions for Second-Order Zarankiewicz Numbers
- Chromatic Extremal Thresholds and the Multipartite K4-Free Problem
- On the exact quantum chromatic number of generalized Johnson graphs
BibTeX
@misc{jiang2026exact,
title = {{Exact and extremal values of 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.13580},
eprint = {2610.13580},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13580},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact and extremal values of 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.13580
UR - https://arxiv.org/abs/2610.13580
AB - Chromatic villainy measures the largest number of vertices that must change color to repair a rearrangement of an optimal coloring while preserving every color multiplicity. Weak villainy allows different multiplicities in the repair. On the odd cycle C_2r+1, we determine the largest repair distance from arbitrary color assignments with a prescribed color-count vector (profile) m to proper colorings with any realizable target profile p: it equals 2r+1−∑_Xmin{p_X,⌈ m_X/2⌉}. In particular, every feasible profile (a,b,c) has ordinary and weak repair radius ⌊ a/2⌋+⌊ b/2⌋+⌊ c/2⌋, and B(C_2r+1)=r for r≥2, answering a question of Clark et al. For arbitrary complete multipartite graphs, we give an arithmetic formula for ordinary villainy with at most k^2 candidates and an exact finite formula for weak villainy, where k is the number of parts. Both values are fixed-parameter tractable in k for binary-encoded part sizes. We also determine the maximum of each parameter among all n-vertex k-chromatic graphs. For k≥3, the ordinary maximum is min{n,4(n−k)}, except when n=4(n−k)−1 or (n,k)∈{(5,3),(7,3)}, when it is n−1. For k≥2, the weak maximum is n−max{⌈ n/k⌉,2k−n}−ε, where ε∈{0,1} is determined explicitly by n and k. Both extrema are attained by complete multipartite graphs, and a weak extremizer needs at most three distinct part sizes.
ER -