View PDF HTML (experimental)

Abstract:A partition $\pi=\{V_{1},V_{2},...,V_{k}\}$ of the vertex set $V$ of a graph $G$ into $k$ color classes $V_{i}$, with $1\leq i\leq k$ is called a quorum coloring of $G$ if for every vertex $v\in 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 quorum coloring number of $G$ and is denoted by $\psi_{q}(G)$. A quorum coloring of order $\psi_{q}(G)$ is a $\psi_{q}$-coloring. The determination of the quorum coloring number or design a linear-time algorithm computing it in a perfect $N$-ary tree has been posed recently as an open problem by Sahbi. In this paper, we answer this problem by designing a linear-time algorithm for finding both a $\psi_{q}$-coloring and the quorum coloring number for every perfect tree whose the vertices at the same depth have the same degree.

Submission history

From: Rafik Sahbi [view email]
[v1] Fri, 5 May 2023 14:44:33 UTC (15 KB)
[v2] Wed, 16 Sep 2026 18:14:03 UTC (16 KB)