Quorum colorings of perfect trees

¹ Department of Fundamental Science and Technology, National Higher School of Advanced Technologies, B.P. 474, Martyrs Square, Algiers 16001, Algeria
² Department of Mathematics, University of Blida 1, B.P. 270, Blida 09000, Algeria

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 20 August 2025
Accepted: 20 December 2025

Abstract

A partition π = {V₁, V₂, …, V_k} of the vertex set V of a graph G into k color classes V_i, 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 order ψ_q(G) is a ψ_q-coloring. In this paper, we determine the exact value of the quorum coloring number of all perfect trees and show that this value is computable in linear time. Moreover, we design a linear-time algorithm that finds a ψ_q-coloring for any perfect tree, which partially answers an open question raised by Hedetniemi et al. [AKCE Int. J. Graphs Comb. 10 (2013) 97–109].