Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8941824 | Discrete Applied Mathematics | 2018 | 6 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Rafik Sahbi, Mustapha Chellali,