Quorum colorings of maximum cardinality in linear time for a subclass of perfect trees

A partition $\pi =\{V_1,V_2,\mathrm{.}\mathrm{.}\mathrm{.},V_k\}$ of the vertex set $V$ of a graph $G$ into $k$ color classes $V_i$, with $1\le i\le 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.