Geodesic
On $P_5$-free locally split graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1063-1090 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

In this paper we study a graph which contains no induced path of five vertices which is known as the P_5-free graph. We prove that every prime P_5-free locally split graph has either a bounded number of vertices, or is a subclass of a (2, 1) split graph, or is a split graph. Then we show that the Minimum Coloring problem (MC) and the maximum independent set problem (MIS) for P_5-free locally split graphs can be both solved in polynomial time.
Keywords: $SP_{5}$-free graphs, modular decomposition, recognition, maximum independent set, minimum coloring 
@article{DMGT_2023_43_4_a10,
     author = {Issaadi, Hayat and Ait Haddadene, Hacene and Kheddouci, Hamamache},
     title = {On $P_5$-free locally split graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1063--1090},
     year = {2023},
     volume = {43},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a10/}
}
TY  - JOUR
AU  - Issaadi, Hayat
AU  - Ait Haddadene, Hacene
AU  - Kheddouci, Hamamache
TI  - On $P_5$-free locally split graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 1063
EP  - 1090
VL  - 43
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a10/
LA  - en
ID  - DMGT_2023_43_4_a10
ER  - 
%0 Journal Article
%A Issaadi, Hayat
%A Ait Haddadene, Hacene
%A Kheddouci, Hamamache
%T On $P_5$-free locally split graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 1063-1090
%V 43
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a10/
%G en
%F DMGT_2023_43_4_a10
Issaadi, Hayat; Ait Haddadene, Hacene; Kheddouci, Hamamache. On $P_5$-free locally split graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1063-1090. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a10/

[1] H. Ait Haddadene and H. Issaadi, Coloring perfect split neighbourhood graphs (CIRO 05', 2005).

[2] H. Ait Haddadene and H. Issaadi, Perfect graphs and vertex coloring problem, IAENG Int. J. Appl. Math. 39 (2009) 128–133.

[3] V.E. Alekseev and V. Lozin, Independent sets of maximum weight in (p; q)-colorable graphs, Discrete Math. 265 (2003) 351–356. https://doi.org/10.1016/S0012-365X(02)00877-4

[4] A. Brandstädt, Partitions of graphs into one or two independent sets and cliques, Discrete Appl. Math. 152 (1996) 47–54. https://doi.org/10.1016/0012-365X(94)00296-U

[5] A. Brandstädt, (P5, diamond)-free graphs revisited: structure and linear time optimization, Discrete Appl. Math. 138 (2004) 13–27. https://doi.org/10.1016/S0166-218X(03)00266-X

[6] A. Brandstädt and D. Kratsch, On the structure of (P5,gem)-free graphs, Discrete Appl. Math. 145 (2005) 155–166. https://doi.org/10.1016/j.dam.2004.01.009

[7] S. Brandt, Triangle-free graphs whose independence number equals the degree, Discrete Math. 310 (2010) 662–669. https://doi.org/10.1016/j.disc.2009.05.021

[8] H.L. Bodlaender, A. Brandstädt, D. Kratsh, M. Rao and J. Spinrad, On algorithms for (P5,gem)-free graphs, Theoret. Comput. Sci. 349 (2005) 2–21. https://doi.org/10.1016/j.tcs.2005.09.026

[9] F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Stein and M. Zhong, 3-colouring graphs without triangles or induced paths on seven vertices (2014), submitted.

[10] V. Chvátal, On certain polytopes associated with graphs, J. Combin. Theory Ser. B 18 (1975) 138–154. https://doi.org/10.1016/0095-8956(75)90041-6

[11] D.G. Corneil, H. Lerchs and L. Stewart-Burlingham, Complement reducible graphs, Disrete Appl. Math. 3 (1981) 163–174. https://doi.org/10.1016/0166-218X(81)90013-5

[12] D.G. Corneil, Y. Perl and L.K. Stewart, Cographs: recognition, applications and algorithms, Congr. Numer. 43 (1984) 249–258.

[13] K. Dabrowski, V. Lozin, R. Raman and B. Ries, Colouring vertices of triangle-free graphs without forests, Discrete Math. 312 (2012) 1372–1385. https://doi.org/10.1016/j.disc.2011.12.012

[14] Z. Dvořák and M. Mnich, Large independent sets in triangle-free planar graphs, Lecture Notes in Comput. Sci. 8737 (2014) 346–357. https://doi.org/10.1007/978-3-662-44777-2_29

[15] A. Frank, Some polynomial algorithms for certain graphs and hypergraphs, in: Proc. Fifth British Combinatorial Conf. Aberdeen 1975, C.Nash-Williams and J. Sheehan (Ed(s)), Congr. Numer. XV (1976) 211–226.

[16] S. Földes and P.L. Hammer, Split graphs, in: 8th S-E Conf.on Combinatorics, Graph Theory and Computing, F. Hoffman et al. (Ed(s)), Congr. Numer. XIX (1977) 311–315.

[17] T. Gallai, Transitiv orientatierbare graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25–66. https://doi.org/10.1007/BF02020961

[18] S. Gaspers, S. Haung and D. Paulusma, Colouring square-free graphs without long induced paths, J. Comput. System Sci. 106 (2019) 60–79. https://doi.org/10.1016/j.jcss.2019.06.002

[19] V. Giakoumakis and I. Rusu, Weighted parameters in (P5, \overline{P5}) graphs, Discrete Appl. Math. 80 (1997) 255–261. https://doi.org/10.1016/S0166-218X(97)00093-0

[20] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, 1980). https://doi.org/10.1016/C2013-0-10739-8

[21] M. Habib and C. Paul, A survey of the algorithmic aspects of modular decomposition, Comput. Sci. Rev. 4 (2010) 41–59. https://doi.org/10.1016/j.cosrev.2010.01.001

[22] P.L. Hammer and B. Simeone, The splittance of a graph, 1 1981 (275–284). https://doi.org/10.1007/BF02579333

[23] R. Hayward, C. Hoàng and F. Maffray, Optimizing weakly triangulated graphs, Graphs Combin. 5 (1989) 339–349. https://doi.org/10.1007/BF01788689

[24] C C. Heckman and R. Thomas, Independent sets in triangle-free cubic planar graphs, J. Combin. Theory Ser. B 96 (2006) 253–275. https://doi.org/10.1016/j.jctb.2005.07.009

[25] C.T. Hoàng and B.A. Reed, Some classes of perfectly orderable graphs, J. Graph Theory 13 (1989) 445–463. https://doi.org/10.1002/jgt.3190130407

[26] C.T. Hoàng, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, Discrete Appl. Math. 55 (1994) 133–143. https://doi.org/10.1016/0166-218X(94)90004-3

[27] C.T. Hoàng, On the structure of (banner, odd hole)-free graphs, J. Graph Theory 89 (2018) 395–412. https://doi.org/10.1002/jgt.22258

[28] D. Lokshtanov, M. Vatshelle and Y. Villanger, Independent set in P5-free graphs in polynomial time, in: Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, C. Chekuri (Ed(s)), (SIAM 2014) 570–58. https://doi.org/10.1137/1.9781611973402.43

[29] V. Lozin, J. Monnot and B. Ries, On the maximum independent set problem in subclasses of subcubic graphs, J. Discrete Algorithms 31 (2015) 104–112. https://doi.org/10.1016/j.jda.2014.08.005

[30] F. Maffray and M. Preissmann, Linear recognition of pseudo-split graphs, Discrete Appl. Math. 52 (1994) 307–312. https://doi.org/10.1016/0166-218X(94)00022-0

[31] N. Matsumoto and M. Tanaka, The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices, Aequationes Math. 95 (2021) 319–328. https://doi.org/10.1007/s00010-020-00760-z

[32] C. McDiarmid and B.A. Reed, Channel assignment and weighted coloring, Networks 36 (2000) 114–117. https://doi.org/10.1002/1097-0037(200009)36:23.0.CO;2-G

[33] R H. Möhring and F J. Radermacher, Substitution decomposition for discrete structures and connections with combinatorial optimization, North-Holland Math. Studies 95 (1984) 257–355. https://doi.org/10.1016/S0304-0208(08)72966-9

[34] M. Rao, Décompositions de Graphes et Algorithmes Efficaces, Ph.D. Thesis (Université Paul Verlaine, Metz, 2006).

[35] P.D. Sumner, Graphs indecomposable with respet to the X-join, Discrete Math. 6 (1973) 281–298. https://doi.org/10.1016/0012-365X(73)90100-3