Discussiones Mathematicae Graph Theory 31(1) (2011)
37-44
doi: 10.7151/dmgt.1528
Andrew Breiner
Department of Mathematics and Computer Science | Jitender Deogun
Department of Computer Science and Engineering | Pierre Ille
C.N.R.S. - UMR 6206 |
Keywords: interval, indecomposable, k-covering, decomposition tree.
2010 Mathematics Subject Classification: 05C20, 05C75.
[1] | R. McConnell and F. de Montgolfier, Linear-time modular decomposition of directed graphs, Discrete Appl. Math. 145 (2005) 198-209, doi: 10.1016/j.dam.2004.02.017. |
[2] | A. Cournier and M. Habib, An efficient algorithm to recognize prime undirected graphs, in: Graph-theoretic Concepts in Computer Science, Lecture Notes in Computer Science 657, E.W. Mayr, (Editor), (Springer, Berlin, 1993) 212-224. |
[3] | A. Ehrenfeucht and G. Rozenberg, Theory of 2-structures. I. Clans, basic subclasses, and morphisms, Theoret. Comput. Sci. 70 (1990) 277-303, doi: 10.1016/0304-3975(90)90129-6. |
[4] | T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25-66, doi: 10.1007/BF02020961. |
[5] | M. Habib, Substitution des structures combinatoires, théorie et algorithmes, Ph.D. Thesis, Université Pierre et Marie Curie, Paris VI, 1981. |
[6] | P. Ille, Indecomposable graphs, Discrete Math. 173 (1997) 71-78, doi: 10.1016/S0012-365X(96)00097-0. |
[7] | D. Kelly, Comparability graphs, in: Graphs and Orders, I. Rival, (Editor), Reidel (Drodrecht, 1985) 3-40. |
[8] | F. Maffray and M. Preissmann, A translation of Tibor Gallai's paper: transitiv orientierbare Graphen, in: Perfect Graphs, J.J. Ramirez-Alfonsin and B.A. Reed, (Editors) (Wiley, New York, 2001) 25-66. |
[9] | J. Schmerl and W. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math. 113 (1993) 191-205, doi: 10.1016/0012-365X(93)90516-V. |
[10] | J. Spinrad, P_{4}-trees and substitution decomposition, Discrete Appl. Math. 39 (1992) 263-291, doi: 10.1016/0166-218X(92)90180-I. |
Received 11 June 2008
Revised 29 March 2010
Accepted 6 April 2010