Solutions to four open problems on quorum colorings of graphs

Department of the Preparatory Training Algiers Higher School of Applied Sciences, B.P. 474, Martyrs Square, Algiers 16001, Algeria.

^* Corresponding author: r.sahbi@g.essa-alger.dz

Received: 31 March 2021
Accepted: 28 July 2021

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 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 ψ_q (G). In this paper, we give answers to four open problems stated in 2013 by Hedetniemi, Hedetniemi, Laskar and Mulder. In particular, we show that there is no good characterization of the graphs G with ψ_q (G) nor for those with ψ_q (G) > 1 unless 𝒫 ≠ 𝒩𝒫 ∩ co – 𝒩𝒫. We also construct several new infinite families of such graphs, one of which the diameter diam (G) of G is not bounded.