×

zbMATH — the first resource for mathematics

Complement reducible graphs. (English) Zbl 0463.05057

MSC:
05C75 Structural characterization of families of graphs
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agarwal, R.K., An investigation of the subgraph isomorphism problem, (), TR 138/80
[2] Arditti, J.C.; DeWerra, D., A note on a paper by D. seinsche, J. combinatorial theory (B), 21, 90, (1976) · Zbl 0297.05108
[3] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), MacMillan New York · Zbl 1134.05001
[4] Booth, K.S.; Colbourn, C.J., Problems polynomially equivalent to graph isomorphism, (1979), Dept. of Comp. Sci., University of Waterloo, TR 77-04
[5] C. Colbourn and M. Colbourn, private communication (1978)
[6] Foulis, D.J., Empirical logic, () · Zbl 0495.03041
[7] Gilmore, P.C.; Hoffman, A.J., A characterization of comparability and of interval graphs, Canad. J. math., 16, 539-548, (1964) · Zbl 0121.26003
[8] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[9] Hopcroft, J.E.; Tarjan, R.E., Isomorphism of planar graphs, () · Zbl 0274.05103
[10] Hopcroft, J.E.; Wong, J.K., Linear time algorithm for isomorphism of planar graphs, Proc. sixth annual ACM symp. on the theory of computing, 172-184, (1974) · Zbl 0369.05028
[11] Jung, H.A., On a class of posets and the corresponding comparability graphs, J. combinatorial theory, 24, B, 125-133, (1978) · Zbl 0382.05045
[12] Klawe, M.M.; Corneil, D.G.; Proskurowski, A., Isomorphism testing in hookup classes, IBM research report RJ3091, (1981), (38307) · Zbl 0503.05023
[13] Lawler, E.L., Graphical algorithms and their complexity, Math. centre tracts, 81, 3-32, (1976) · Zbl 0358.68059
[14] Lerchs, H., On cliques and kernels, (March 1971), Dept. of Comp. Sci., University of Toronto
[15] Lerchs, H., On the clique-kernel structure of graphs, (October 1972), Dept. of Comp. Sci., University of Toronto
[16] Leuker, G.S.; Booth, K.S., A linear time algorithm for deciding interval graph isomorphism, J. assoc. comput. Mach., 26, 2, 183-195, (1979) · Zbl 0402.68050
[17] MacMahon, P.A., The combination of resistances, The Electrician, 28, 601-602, (1892)
[18] Moon, J.W.; Moser, L., On cliques in graphs, Israel J. math., 3, 23-28, (1965) · Zbl 0144.23205
[19] Payan, C., A class of threshold and domishold graphs: equistable and equidominating graphs, Discrete math., 29, 47-52, (1980) · Zbl 0542.05050
[20] Riordan, J., An introduction to combinatorial analysis, (), 139-143
[21] Seinsche, D., On a property of the class of n-colorable graphs, J. combinatorial theory (B), 16, 191-193, (1974) · Zbl 0269.05103
[22] Stewart, L., Cographs, a class of tree representable graphs, (), TR 126/78
[23] Sumner, D.P., Dacey graphs, J. Australian math. soc., 18, 4, 492-502, (1974) · Zbl 0314.05108
[24] Valdes, J.; Tarjan, R.E.; Lawler, E.L., The recognition of series parallel digraphs, Proc. eleventh annual ACM symp. on the theory of computing, 1-12, (1979)
[25] Wolk, E.S., The comparability graph of a tree, Proc. AMS, 13, 789-795, (1962) · Zbl 0109.16402
[26] Wolk, E.S., A note on ‘the comparability graph of a tree’, Proc. AMS, 16, 17-20, (1965) · Zbl 0137.18105
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.