Geodesic
Disjoint maximal independent sets in graphs and hypergraphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1361-1371 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

In this paper, we consider the question of the existence of disjoint maximal independent sets (MIS) in graphs and hypergraphs. The question was raised in the 1970's independently by Berge and Payan. They considered the question of characterizing the graphs that admit disjoint MIS, and in particular whether regular graphs do. In this paper, we are interested in the existence of disjoint MIS in a graph or in its complement, motivated by the fact that most constructions of graphs that do not admit disjoint MIS are such that their complement does. We prove that there are disjoint MIS in a graph or its complement whenever the graph has diameter at least three or has chromatic number at most four. We also define a graph of chromatic number 5 and diameter 2 which does not admit disjoint MIS nor its complement. As our work was first motivated by a more recent work on disjoint MIS in hypergraphs by Acharya (2010), we also consider the question of the existence of disjoint MIS in hypergraphs. We answer a question by Jose and Tuza (2009), proving that there exists balanced k-connected hypergraphs admitting no disjoint MIS.
Keywords: maximal independent set, clique, disjoint sets 
@article{DMGT_2024_44_4_a7,
     author = {Dorbec, Paul and Kaci, Fatma},
     title = {Disjoint maximal independent sets in graphs and hypergraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1361--1371},
     year = {2024},
     volume = {44},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a7/}
}
TY  - JOUR
AU  - Dorbec, Paul
AU  - Kaci, Fatma
TI  - Disjoint maximal independent sets in graphs and hypergraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1361
EP  - 1371
VL  - 44
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a7/
LA  - en
ID  - DMGT_2024_44_4_a7
ER  - 
%0 Journal Article
%A Dorbec, Paul
%A Kaci, Fatma
%T Disjoint maximal independent sets in graphs and hypergraphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1361-1371
%V 44
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a7/
%G en
%F DMGT_2024_44_4_a7
Dorbec, Paul; Kaci, Fatma. Disjoint maximal independent sets in graphs and hypergraphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1361-1371. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a7/

[1] B.D. Acharya, Domination in hypergraphs II}: New directions, in: Recent Trends in Discrete Mathematics, Mysore, 2008, B.D. Acharya, G.O.H. Katona and J. Nešetřil (Ed(s)), (Ramanujan Math. Soc. Lect. Notes Ser. Math. 2010) 1–18.

[2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Elsevier Science Publishing Co., Inc., New York, 1976).

[3] E.J. Cockayne and S.T. Hedetniemi, Disjoint independent dominating sets in graphs, Discrete Math. 15 (1976) 213–222. https://doi.org/10.1016/0012-365X(76)90026-1

[4] P. Erdős, A.M. Hobbs and C. Payan, Disjoint cliques and disjoint maximal independent sets of vertices in graphs, Discrete Math. 42 (1982) 57–61. https://doi.org/10.1016/0012-365X(82)90053-X

[5] W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013) 839–854. https://doi.org/10.1016/j.disc.2012.11.031

[6] M.A. Henning, C. Löwenstein and D. Rautenbach, Remarks about disjoint dominating sets, Discrete Math. 309 (2009) 6451–6458. https://doi.org/10.1016/j.disc.2009.06.017

[7] B.K. Jose and Zs. Tuza, Hypergraph domination and strong independence, Appl. Anal. Discrete Math. 3 (2009) 347–358. https://doi.org/10.2298/AADM0902347J

[8] C. Payan, Coverings by minimal transversals, Discrete Math. 23 (1978) 273–277. https://doi.org/10.1016/0012-365X(78)90008-0

[9] C. Payan, Sur une classe de problèmes de couverture, C.R. Acad. Sci. Paris Sér. A 278 (1974) 233–235.

[10] C. Payan, A counter-example to the conjecture "every nonempty regular simple graph contains two disjoint maximal independent sets", Graph Theory Newsletter 6 (1977) 7–8.

[11] O. Schaudt, On disjoint maximal independent sets in graphs, Inform. Process. Lett. 115 (2015) 23–27. https://doi.org/10.1016/j.ipl.2014.08.010