On some open problems concerning quorum colorings of graphs

摘要

A partitionπ={V1,V2,…,Vk}of the vertex setVof a graphGintokcolor classesVi,withi∈{1,…,k},is called a quorum coloring if, for every vertexv∈V,at least half of the vertices in the closed neighborhoodN[v]ofvhave the same color asv. The maximum order of a quorum coloring ofGis called the quorum coloring number ofGand 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?Gonnvertices,ψq(G)+ψq(Gˉ)≤n+2,whereGˉis the complement ofG.