On some open problems concerning quorum colorings of graphs

A partition π={V1,V2,…,Vk} of the vertex set V of a graph G into k color classes Vi, with i∈{1,…,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 order 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 three open problems stated in 2013 by Hedetniemi, Hedetniemi, Laskar and Mulder. In particular, we show that the decision problem associated with ψq(G) is NP-complete, and we prove that for any graph G on n vertices, ψq(G)+ψq(G¯)≤n+2, where G¯ is the complement of G.