no. 4
Solutions to four open problems on quorum colorings of graphs
RAIRO. Operations Research, Tome 55 (2021) no. 4, pp. 2385-2394
corrigé par Erratum to: Solutions to four open problems on quorum colorings of graphs

A partition π = {V1, V2,…,V$$} of the vertex set V of a graph G into k color classes V$$, 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 ψ$$ (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 ψ$$ (G) nor for those with ψ$$ (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.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2021116
Classification : 05C15, 05C69
Keywords: Defensive alliances, quorum colorings, good characterizations, complexity, diameter 
@article{RO_2021__55_4_2385_0,
     author = {Sahbi, Rafik},
     title = {Solutions to four open problems on quorum colorings of graphs},
     journal = {RAIRO. Operations Research},
     pages = {2385--2394},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {4},
     doi = {10.1051/ro/2021116},
     mrnumber = {4297818},
     zbl = {1476.05060},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021116/}
}
TY  - JOUR
AU  - Sahbi, Rafik
TI  - Solutions to four open problems on quorum colorings of graphs
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 2385
EP  - 2394
VL  - 55
IS  - 4
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021116/
DO  - 10.1051/ro/2021116
LA  - en
ID  - RO_2021__55_4_2385_0
ER  - 
%0 Journal Article
%A Sahbi, Rafik
%T Solutions to four open problems on quorum colorings of graphs
%J RAIRO. Operations Research
%D 2021
%P 2385-2394
%V 55
%N 4
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021116/
%R 10.1051/ro/2021116
%G en
%F RO_2021__55_4_2385_0
Sahbi, Rafik. Solutions to four open problems on quorum colorings of graphs. RAIRO. Operations Research, Tome 55 (2021) no. 4, pp. 2385-2394. doi: 10.1051/ro/2021116

[1] C. Bazgan, Z. Tuza, D. Vanderpooten, Satisfactory graph partition, variants, and generalizations. Eur. J. Oper. Res. 206 (2010) 271–280. | MR | Zbl | DOI

[2] J. Edmonds, Minimum partition of a matrloid into independent subsets. J. Res. Nat. Bur. Standards Sect. B 69 (1965) 67–72. | MR | Zbl | DOI

[3] L. Eroh, R. Gera, Alliance partition number in graphs. Ars Comb. 103 (2012) 519–529. | MR | Zbl

[4] G. H. Fricke, L. M. Lawson, T. W. Haynes, S. M. Hedetniemi and S. T. Hedetniemi, A note on defensive alliances in graphs. Bull. ICA 38 (2003) 37–41. | MR | Zbl

[5] T. W. Haynes, J. A. Lachniet, The alliance partition number of grid graphs. AKCE Int. J. Graphs Combin. 4 (2007) 51–59. | MR | Zbl

[6] S. M. Hedetniemi, S. T. Hedetniemi, P. Kristiansen, Alliances in graphs. J. Combin. Math. Combin. Comput. 48 (2004) 157–177. | MR | Zbl

[7] S. M. Hedetniemi, S. T. Hedetniemi, R. Laskar, H. M. Mulder, Quorum colorings of graphs. AKCE Int. J. Graphs Comb. 10 (2013) 97–109. | MR | Zbl

[8] M. Olsen, M. Revsbæk, On Alliance Partitions and Bisection Width for Planar Graphs. J. Graph Algorithms Appl. 17 (2013) 599–614. | MR | Zbl | DOI

[9] K. Ouazine, H. Slimani, A. Tari, Alliances in graphs: Parameters, poperties and applications-A survey. AKCE Int. J. Graphs Comb. 15 (2018) 115–154. | MR | Zbl | DOI

[10] R. Sahbi, On the complexity of some quorum colorings problems of graphs. AKCE Int. J. Graphs Comb. 17 (2020) 784–787. | MR | Zbl | DOI

[11] R. Sahbi, M. Chellali, On some open problems concerning quorum colorings of graphs. Discrete Appl. Math. 247 (2018) 294–299. | MR | Zbl | DOI

[12] K. H. Shafique, Partitioning a graph in alliances and its application to data clustering. Ph.D. thesis in Computer Science, University of Central Florida (2004).

[13] K. H. Shafique, R. D. Dutton, On satisfactory partitioning of graphs. Congr. Numer. 154 (2002) 183–194. | MR | Zbl

[14] M. Stiebitz, Decomposing graphs under degree constraints. J. Graph Theory 23 (1996) 321–324. | MR | Zbl | DOI

Cité par Sources :