# Stable sets for $(P\u2086,{K}_{2,3})$-free graphs

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 3, page 387-401
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topRaffaele Mosca. "Stable sets for $(P₆,K_{2,3})$-free graphs." Discussiones Mathematicae Graph Theory 32.3 (2012): 387-401. <http://eudml.org/doc/270954>.

@article{RaffaeleMosca2012,

abstract = {The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for $(P₆,K_\{2,3\})$-free graphs in polynomial time, extending some known results.},

author = {Raffaele Mosca},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph algorithms; stable sets; P₆-free graphs; -free graphs},

language = {eng},

number = {3},

pages = {387-401},

title = {Stable sets for $(P₆,K_\{2,3\})$-free graphs},

url = {http://eudml.org/doc/270954},

volume = {32},

year = {2012},

}

TY - JOUR

AU - Raffaele Mosca

TI - Stable sets for $(P₆,K_{2,3})$-free graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 3

SP - 387

EP - 401

AB - The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for $(P₆,K_{2,3})$-free graphs in polynomial time, extending some known results.

LA - eng

KW - graph algorithms; stable sets; P₆-free graphs; -free graphs

UR - http://eudml.org/doc/270954

ER -

## References

top- [1] V.E. Alekseev, On the local restriction effect on the complexity of finding the graph independence number in: Combinatorial-algebraic Methods in Applied Mathematics, (Gorkiy University Press, Gorkiy, 1983) 3-13 (in Russian).
- [2] V.E. Alekseev, A polynomial algorithm for finding largest independent sets in fork-free graphs, Discrete Anal. Oper. Res., Ser. 1, 6 (1999) 3-19 (in Russian) (see also [3] for the English version).
- [3] V.E. Alekseev, A polynomial algorithm for finding largest independent sets in fork-free graphs, Discrete Applied Math. 135 (2004) 3-16, doi: 10.1016/S0166-218X(02)00290-1.
- [4] V.E. Alekseev, On easy and hard hereditary classes of graphs with respect to the independent set problem, Discrete Applied Math. 132 (2004) 17-26, doi: 10.1016/S0166-218X(03)00387-1.
- [5] V.E. Alekseev and V.V. Lozin, Augmenting graphs for independent sets, Discrete Applied Math. 145 (2004) 3-10, doi: 10.1016/j.dam.2003.09.003. Zbl1056.05131
- [6] G. Bacsó and Zs. Tuza, A characterization of graphs without long induced paths, J. Graph Theory 14 (1990) 455-464, doi: 10.1002/jgt.3190140409.
- [7] A. Brandstädt and Chính T. Hoáng, On clique separators, nearly chordal graphs and the Maximum Weight Stable Set problem, Theoretical Computer Science 389 (2007)) 295-306, doi: 10.1016/j.tcs.2007.09.031. Zbl1143.68059
- [8] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Math. Appl. (vol. 3, SIAM, Philadelphia, 1999). Zbl0919.05001
- [9] A. Brandstädt, T. Klembt and S. Mahfud, P₆- and Triangle-Free Graphs Revisited: Structure and Bounded Clique-Width, Discrete Math. and Theoretical Computer Science 8 (2006) 173-188. Zbl1153.05040
- [10] J. Dong, On the i-diameter of i-center in a graph without long induced paths, J. Graph Theory 30 (1999) 235-241, doi: 10.1002/(SICI)1097-0118(199903)30:3<235::AID-JGT8>3.0.CO;2-C. Zbl0922.05024
- [11] M. Farber, On diameters and radii of bridged graphs, Discrete Math. 73 (1989) 249-260, doi: 10.1016/0012-365X(89)90268-9. Zbl0667.05036
- [12] J.-L. Fouquet, V. Giakoumakis and J.-M. Vanherpe, Bipartite graphs totally decomposable by canonical decomposition, International J. Foundations of Computer Science 10 (1999) 513-533, doi: 10.1142/S0129054199000368. Zbl1320.05093
- [13] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completness (Freeman, San Francisco, CA, 1979). Zbl0411.68039
- [14] M.U. Gerber, A. Hertz and V.V. Lozin, Stable sets in two subclasses of banner-free graphs, Discrete Applied Math. 132 (2004) 121-136, doi: 10.1016/S0166-218X(03)00395-0. Zbl1029.05145
- [15] M.U. Gerber and V.V. Lozin, On the stable set problem in special P₅-free graphs, Discrete Applied Math. 125 (2003) 215-224, doi: 10.1016/S0166-218X(01)00321-3. Zbl1028.05103
- [16] V. Giakoumakis and J.-M. Vanherpe, Linear time recognition and optimization for weak-bisplit graphs, bi-cographs and bipartite P₆-free graphs, International J. Foundations of Computer Science 14 (2003) 107-136, doi: 10.1142/S0129054103001625. Zbl1099.68680
- [17] A. Hertz and V.V. Lozin The maximum independent set problem and augmenting graphs, Graph Theory and Combinatorial Optimization, GERAD 25th Anniv., Springer, New York (2005) 69-99.
- [18] P. van't Hof and D. Paulusma, A new characterization of P₆-free graphs, Discrete Applied Math. 158 (2010) 731-740, doi: 10.1016/j.dam.2008.08.025. Zbl1225.05145
- [19] J. Liu, Y. Peng and C. Zhao, Characterization of P₆-free graphs, Discrete Applied Math. 155 (2007) 1038-1043, doi: 10.1016/j.dam.2006.11.005. Zbl1117.05082
- [20] J. Liu and H. Zhou, Dominating subgraphs in graphs with some forbidden structure, Discrete Math. 135 (1994) 163-168, doi: 10.1016/0012-365X(93)E0111-G. Zbl0812.05052
- [21] V.V. Lozin and M. Milanič, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, J. Discrete Algorithms 6 (2008) 595-604, doi: 10.1016/j.jda.2008.04.001. Zbl1154.90607
- [22] V.V. Lozin and M. Milanič, On finding augmenting graphs, Discrete Applied Math. 156 (2008) 2517-2529, doi: 10.1016/j.dam.2008.03.008. Zbl1159.05313
- [23] V.V. Lozin and R. Mosca, Independent sets in extensions of 2K₂-free graphs, Discrete Applied Math. 146 (2005) 74-80, doi: 10.1016/j.dam.2004.07.006. Zbl1087.90080
- [24] V.V. Lozin and D. Rautenbach, Some results on graphs without long induced paths, Information Processing Letters 88 (2003) 167-171, doi: 10.1016/j.ipl.2003.07.004. Zbl1178.68285
- [25] G.J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory (B) 28 (1980) 284-304, doi: 10.1016/0095-8956(80)90074-X. Zbl0434.05043
- [26] R. Mosca, Stable sets in certain P₆-free graphs, Discrete Applied Math. 92 (1999) 177-191, doi: 10.1016/S0166-218X(99)00046-3. Zbl0929.05076
- [27] R. Mosca, Some observations on maximum weight stable sets in certain P₅-free graphs, European J. Operational Research 184 (2008) 849-859, doi: 10.1016/j.ejor.2006.12.011. Zbl1141.05068
- [28] R. Mosca, Independent sets in (P₆,diamond)-free graphs, Discrete Math. and Theoretical Computer Science 11:1 (2009) 125-140. Zbl1196.05065
- [29] O.J. Murphy, Computing independent sets in graphs with large girth, Discrete Applied Math. 35 (1992) 167-170, doi: 10.1016/0166-218X(92)90041-8. Zbl0769.05053
- [30] N. Sbihi, Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile, Discrete Math. 29 (1980) 53-76, doi: 10.1016/0012-365X(90)90287-R. Zbl0444.05049

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.