Sub-quorum colorings of graphs
Abstract
A sub-quorum coloring is a partial vertex coloring in which every colored vertex sees at least half of its colored closed neighborhood in its own color. We study the maximum number of colors psq(G) from structural, algorithmic and extremal viewpoints. Every $2$-independent set yields a sub-quorum coloring, so psq(G)≥β2(G). We prove the degree bound psq(G)≤ Δ(G)|V(G)|/(Δ(G)+δ(G)−1) for δ(G)≥2, and obtain an exact matching characterization for graphs of maximum degree at most three. Consequently every cubic graph of order n satisfies n/2≤psq(G)≤3n/5, with a stability identity at the upper endpoint. For trees we give an edge representation and a linear-time dynamic program that computes both psq(T) and an optimal coloring; we also show on the double star S2,2 that psq can exceed the dissociation number even on trees. We prove NP-completeness even for bipartite graphs and determine exact values for several classical families. For rectangular grids, we formulate the conjecture psq(Gm,n)=β2(Gm,n)=F(m,n), recover the dissociation-number formula from known $3$-path vertex-cover results, prove the ladder case directly, and verify the conjecture for every fixed width 2≤ m≤11; widths $3$ through $11$ use exact transfer certificates. For hypercubes we prove psq(Qn)=β2(Qn)=2n−1 for every n≥2. Finally, a Nordhaus--Gaddum argument gives psq(G)+psq(G̅)>log2 |V(G)| and leads to a complementary upper-bound problem.
Related
- Sub-quorum colorings of some infinite families of caterpillars
- Cayley graphs of abelian groups, circular colorings and discrete fundamental groups
- On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
- Optimal Kt-free list colorings and the Pollyanna property of graphs with no triangular wheel
- Sequence b-colorings in graphs
BibTeX
@misc{ma2026subquorum,
title = {{Sub-quorum colorings of graphs}},
author = {Haobo Ma and Rafik Sahbi and Zhang Wenlin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.25128},
eprint = {2609.25128},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25128},
}
RIS
TY - UNPB
TI - Sub-quorum colorings of graphs
AU - Haobo Ma
AU - Rafik Sahbi
AU - Zhang Wenlin
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2609.25128
UR - https://arxiv.org/abs/2609.25128
AB - A sub-quorum coloring is a partial vertex coloring in which every colored vertex sees at least half of its colored closed neighborhood in its own color. We study the maximum number of colors psq(G) from structural, algorithmic and extremal viewpoints. Every $2$-independent set yields a sub-quorum coloring, so psq(G)≥β_2(G). We prove the degree bound psq(G)≤ Δ(G)|V(G)|/(Δ(G)+δ(G)−1) for δ(G)≥2, and obtain an exact matching characterization for graphs of maximum degree at most three. Consequently every cubic graph of order n satisfies n/2≤psq(G)≤3n/5, with a stability identity at the upper endpoint. For trees we give an edge representation and a linear-time dynamic program that computes both psq(T) and an optimal coloring; we also show on the double star S_2,2 that psq can exceed the dissociation number even on trees. We prove NP-completeness even for bipartite graphs and determine exact values for several classical families. For rectangular grids, we formulate the conjecture psq(G_m,n)=β_2(G_m,n)=F(m,n), recover the dissociation-number formula from known $3$-path vertex-cover results, prove the ladder case directly, and verify the conjecture for every fixed width 2≤ m≤11; widths $3$ through $11$ use exact transfer certificates. For hypercubes we prove psq(Q_n)=β_2(Q_n)=2^n−1 for every n≥2. Finally, a Nordhaus--Gaddum argument gives psq(G)+psq(G̅)>log_2 |V(G)| and leads to a complementary upper-bound problem.
ER -