1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On P5-Free Locally Split Graphs

Published Online: 05 Aug 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 01 Dec 2020
Accepted: 28 Jun 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

In this paper we study a graph which contains no induced path of five vertices which is known as the P5-free graph. We prove that every prime P5-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 P5-free locally split graphs can be both solved in polynomial time.

Keywords

MSC 2010

[1] H. Ait Haddadene and H. Issaadi, Coloring perfect split neighbourhood graphs (CIRO 05’, 2005).Search in Google Scholar

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

[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-410.1016/S0012-365X(02)00877-4Search in Google Scholar

[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-U10.1016/0012-365X(94)00296-USearch in Google Scholar

[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-X10.1016/S0166-218X(03)00266-XSearch in Google Scholar

[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.00910.1016/j.dam.2004.01.009Search in Google Scholar

[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.02110.1016/j.disc.2009.05.021Search in Google Scholar

[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.02610.1016/j.tcs.2005.09.026Search in Google Scholar

[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.Search in Google Scholar

[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-610.1016/0095-8956(75)90041-6Search in Google Scholar

[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-510.1016/0166-218X(81)90013-5Search in Google Scholar

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

[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.01210.1016/j.disc.2011.12.012Search in Google Scholar

[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 2910.1007/978-3-662-44777-2Search in Google Scholar

[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.Search in Google Scholar

[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.Search in Google Scholar

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

[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.00210.1016/j.jcss.2019.06.002Search in Google Scholar

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

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

[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.00110.1016/j.cosrev.2010.01.001Search in Google Scholar

[22] P.L. Hammer and B. Simeone, The splittance of a graph, Combinatorica 1 (1981) 275–284. https://doi.org/10.1007/BF0257933310.1007/BF02579333Search in Google Scholar

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

[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.00910.1016/j.jctb.2005.07.009Search in Google Scholar

[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.319013040710.1002/jgt.3190130407Search in Google Scholar

[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-310.1016/0166-218X(94)90004-3Search in Google Scholar

[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.2225810.1002/jgt.22258Search in Google Scholar

[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.4310.1137/1.9781611973402.43Search in Google Scholar

[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.00510.1016/j.jda.2014.08.005Search in Google Scholar

[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-010.1016/0166-218X(94)00022-0Search in Google Scholar

[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-z10.1007/s00010-020-00760-zSearch in Google Scholar

[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-GSearch in Google Scholar

[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-910.1016/S0304-0208(08)72966-9Search in Google Scholar

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

[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-310.1016/0012-365X(73)90100-3Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo