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

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\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.

arXiv commentI replace the old version by the exactly same version by mistake. Nothing changes