DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

H. Issaadi

Hayat Issaadi

USTHB university

email: issaadihayat@yahoo.fr

H. Ait Haddadene

Hacene Ait Haddadene

USTHB University

email: hait-haddadene@usthb.dz

H. Kheddouci

Hamamache Kheddouci

Claude Bernard Lyon 1

email: hamamache.kheddouci@univ-lyon1.fr

Title:

On $P_5$-free locally split graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 43(4) (2023) 1063-1090

Received: 2020-12-01 , Revised: 2021-06-28 , Accepted: 2021-06-28 , Available online: 2021-07-10 , https://doi.org/10.7151/dmgt.2418

Abstract:

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

References:

  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, $(P_{5}$, 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 $(P_{5}$,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 $(P_{5}$,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 $(P_{5}, \overline{P_{5}})$ 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 $P_5$-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:2<114::AID-NET6>3.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
Close