Sub-quorum colorings of some infinite families of caterpillars
Abstract
A partition π={V1,V2,...,Vk} of the vertex set V of a graph G into k color classes Vi, with i∈{1,...,k} is called a {\it quorum coloring} if for every vertex v∈ V, at least half of the vertices in the closed neighborhood N[v] of v have the same color as v. The maximum cardinality of a quorum coloring of G is called the {\it quorum coloring number} of G and is denoted by ψq(G). A {\it sub-quorum coloring} of G is an onto partial function f:V→{1,2,…,ℓ} having the property that for every vertex v∈ V, if f(v) is defined, then at least half of the vertices in N[v] having an image by f, have the same color as v. The {\it sub-quorum coloring number} ψsq(G) equals the maximum value ℓ in a sub-quorum coloring of G. In this paper, we determine the exact value of the sub-quorum coloring number for some infinite families of caterpillars including complete n-tuple caterpillars and complete caterpillars with minimum spine-vertex degree three.
Related
- Global log canonical thresholds for Burniat surfaces and some infinite families of surfaces of general type as ℤ2n-covers
- Some Infinite Families of Arithmetic Symplectic Hypergeometric Groups
- On the Average Sizes of Ideals and Antichains in Some Infinite Families of Posets
- Sub-quorum colorings of graphs
- Colorings breaking prescribed families of graph automorphisms
BibTeX
@misc{sahbi2026subquorum,
title = {{Sub-quorum colorings of some infinite families of caterpillars}},
author = {Rafik Sahbi and Youcef Belkina and Amar Bennadji},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39619},
eprint = {2609.39619},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39619},
}
RIS
TY - UNPB
TI - Sub-quorum colorings of some infinite families of caterpillars
AU - Rafik Sahbi
AU - Youcef Belkina
AU - Amar Bennadji
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39619
UR - https://arxiv.org/abs/2609.39619
AB - A partition π={V_1,V_2,...,V_k} of the vertex set V of a graph G into k color classes V_i, with i∈{1,...,k} is called a {\it quorum coloring} if for every vertex v∈ V, at least half of the vertices in the closed neighborhood N[v] of v have the same color as v. The maximum cardinality of a quorum coloring of G is called the {\it quorum coloring number} of G and is denoted by ψ_q(G). A {\it sub-quorum coloring} of G is an onto partial function f:V→{1,2,…,ℓ} having the property that for every vertex v∈ V, if f(v) is defined, then at least half of the vertices in N[v] having an image by f, have the same color as v. The {\it sub-quorum coloring number} ψ_sq(G) equals the maximum value ℓ in a sub-quorum coloring of G. In this paper, we determine the exact value of the sub-quorum coloring number for some infinite families of caterpillars including complete n-tuple caterpillars and complete caterpillars with minimum spine-vertex degree three.
ER -