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

A partition π = {V1, V2, …, Vk} of the vertex set V of a graph G into k color classes Vi, with 1 ≤ i ≤ k is called a quorum coloring of G 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 quorum coloring number of G and is denoted by ψq(G). A quorum coloring of G of order ψq(G) is a ψq-coloring of G. In this paper, we design a linear-time algorithm for finding both a ψq-coloring and the quorum coloring number for every perfect tree whose the vertices of the same level have the same degree.