Logo

Bibliography

B.D. Acharya, M.N. Vartak, Open neighbourhood graphs (abstract) Graph Theory Newsletter 2(4) (1973)

C. Berge, Les graphes dŽintervalles, ...

L.W. Beineke, On derived graphs and digraphs, in: Beiträge zur Graphentheorie (Manebach 1967) 17-24.

P. Buneman, A characterization on rigid circuit graphs, Discrete Math. 9 (1974), 205-212.

B. Bollobas, P. Erdös, J. Spencer, D.B. West, Clique coverings of the edges of a random graph, Combinatorica 13 (1993) 1-5.

P.A. Bernstein, N. Goodman, Power of natural semijoins, SIAM J. Comput. 10 (1981) 751-771.

J.C. Bermond, M.C. Heydemann, D. Sotteau, Line graphs of hypergraphs I, Discrete Math. 18 (1977) 235-241.

H. Breu, D.G. Kirkpatrick, Unit disk graph recognition is NP-hard, Comput. Geom. 9 (1998) 3-24.

K.S. Booth, G.S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, JCSS 13 (1976) 335-379.

R. Balakrishnan, P. Paulraja, Powers of chordal graphs, J. Aust. Math. Soc. A 35 (1983) 211-217.

E. Balas, C.-S. Yu, On graphs with polynomially solvable maximum-weight clique problem, Networks 19 (1989) 247-253.

B.N. Clark, C.J. Colbourn, D.S. Johnson, Unit disk graphs, Discrete Math. 86 (1990) 165-177.

V. Chvatal, C. Ebenegger, A note on line digraphs and the directed max-cut problem, Discrete Applied Math. 29 (1990) 165-170.

C.H. Dowker, Homology groups of relations, Ann. of Math. 56 (1952) 84-95.

P. Duchet, Classical perfect graphs, Annals of Discrete Math. 21 (1984) 67-96.

P. Damaschke, Distances in cocomparability graphs and their powers, Discrete Applied Math. 35 (1992) 67-72.

R.D. Dutton, R.C. Brigham, A characterization of competition graphs, Discrete Appl. Math. 6 (1983) 315-317.

B. Dushnik, E.W. Miller, Partially ordered sets, Amer. Math. J. 63 (1941) 600-610.

F. Escalante, Über iterierte Cliquen-Graphen, Abh. Math. Sem. Univ. Hamburg 39 (1973) 58-68.

P. Erdös, A.W. Goodman, L. Posa, The representation of a graph by set intersection, Canad. J. Math. 18 (1966) 106-112.

N. Eaton, R.J. Gould, V. Rödl, On p-intersection representations, J. Graph Th. 21 (1996) 377-382.

C. Flotow, Potenzen von Graphen, Dissertation Universität Hamburg (1995).

Z. Füredi, Intersection representations of the complete bipartite graph, Algorithms Comb. 14 (1997) 86-92.

M.R. Fellows, J. Kratochvil, M. Middendorf, F. Pfeiffer, The complexity of induced minors and related problems, Algorithmica 13 (1995) 266-282.

F. Gavril, The intersection graphs of subtrees of a tree are exactly the chordal graphs, J. Comb. Theory B 16 (1974), pp. 46-56.

M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980.

M.C. Golumbic, D. Rotem, J. Urrutia, Comparability graphs and intersection graphs, Discrete Math. 43 (1983) 37-46.

G. Hajos, Über eine Art von Graphen, Internat. Math. Nachr. 11 (1957).

B. Hedman, Clique graphs of time graphs, J. Comb. Th. B 37 (1984) 270-278.

B. Hedman, Diameters of iterated clique graphs, Hadronic J. 9 (1986) 273-276.

P. Hlineny, J. Kratochvil, Computational complexity of the Krausz dimension of graphs, WG97 LNCS1335 214-228.

M.C. Heydemann, D. Sotteau, Line graphs of hypergraphs II, Colloq. Math. Soc. J. Bolyai 18 (1976) 567-582.

M.S. Jacobson, A.E. Kezdy, J. Lehel, Intersection graphs associated with uniform hypergraphs, Congressus Numerantium 116 (1996) 173-192.

M.S. Jacobson, A.E. Kezdy, J. Lehel, Recognizing intersection graphs of linear uniform hypergraphs, preprint.

M.S. Jacobson, A.E. Kezdy, J. Lehel, Recognizing triangle-free graphs with induced path-cycle double covers is NP-complete, ...?

J. Justicz, E.R. Scheinermann, P.M. Winkler, Random intervals, Amer. Math. Monthly 97 (1990) 881-889.

J. Krausz, D'emonstration nouvelle d'un th'eor`eme de Whitney sur les r'eseaux, Mat. Fiz. Lapok 50 (1943) 75-85.

J. Kratochvil, A special planar satisfiability problem and a consequence of its NP-completeness, Discrete Applied Math. 52 (1994) 233-252.

J. Kratochvil, A. Kubena, On the intersection representation of co-planar graphs, Discrete Math. (1997).

J. Kratochvil, J. Nesetril, Independent Set and Clique problems in intersection-defined classes of graphs, Comment. Mat. Univ. Carolinae 31 (1990) 85-93.

S.F. Kapoor, B.P. Mull, R.G. Rieper, H.C. Swart, Generalized line graphs: a Krausz characterization, Scientia, Ser. A (1988) 75-82.

L.T. Kou, L.J. Stockmeyer, C.K. Wong, Covering edges by cliques with regard to keyword conflicts and intersection graphs, Commun. ACM 21 (1978) 135-139.

J. Leray, Sur la forme des espaces topologiques et sur les points fixes des representations, J. Math. Pures et Appl. 24 (1945) 95-167.

C. Lekkerkerker, J. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math. 51 (1962) 45-64.

P.G.H. Lehot, An optimal algorithm to detect a line graph and output its root graph, J. Assoc. Comput. Mach. 21 (1974) 569-575.

V.B. Le, E. Prisner, Facet graphs of pure simplicial complexes and related concepts, Hamburger Beitraege zur Mathematik, Heft 19 (1992).

C. Lund, M. Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM 41 (1994) 960-981.

J.R. Lundgren, Food webs, competition graphs, competition-common enemy graphs, and niche graphs, in: Applications of Combinatorics and Graph Theory to the Biological Sciences (F.S. Roberts, ed.), Springer (1989) 221-243.

E. Marczewski, Sur deux propri'et'es des classes d`ensembles, Fund. Math. 33 (1945) 303-307.

H. Maehara, The intersection graph of random sets, Discrete Math. 87 (1991) 97-104.

T.A. McKee, Chordal and interval multigraphs, Proceedings of the 6th Conference on Graph Theory, Combinatorics, and Applications, Kalamazoo 1988 (1991) 841-848. Graph Theory, Combinatorics, and Algorithms,

T.A. McKee, Foundations of intersection graph theory, Utilitas Math. 40 (1991) 77-86.

T.A. McKee, A survey on connection graphs, Proceedings of the 7th Conference on Graph Theory, Combinatorics, Algorithms and Applications, Kalamazoo 1992 (1995).

T.A. McKee, F.R. McMorris, Topics in Intersection Graph Theory, SIAM Monograph on Discrete Math. and Appl., 1999.

H. Müller, Recognizing interval digraphs and interval bigraphs in polynomial time, Discrete Applied Math. 78 (1997) 189-205; Erratum, preprint 1999, 4 pages.

Y. Metelsky, E. Prisner, S. Suzdal, R. Tychkevich, Recognizing large-degree intersection graphs of linear 3-uniform hypergraphs, in preparation.

Y. Metelsky, R. Tyshkevich, On line graphs of linear 3-uniform hypergraphs, J. Graph Th. (1997) 241- 251.

R. Motwani, M. Sudan, Computing roots of graphs is hard, Discrete Appl. Math. 54 (1994) 81-88.

A. Mukhopadhyay, The square root of a graph, J. Combin. Th. 2 (1967) 290-295.

R.N. Naik, S.B. Rao, S.S. Shrikhande, N.M. Singhi, Intersection graphs of k-uniform linear hypergraphs, Europ. J. Comb. 3 (1982) 159-172.

E. Prisner, Homology of the line graph and of related graph-valued functions, Arch. Math. (1991) 400-404.

E. Prisner, Graphs with few cliques, Proceedings of the 7th Conference on Graph Theory, Combinatorics, Algorithms and Applications, Kalamazoo 1992 (1995) 945-956.

E. Prisner, Line graphs and generalizations --- a survey, in: Surveys in Graph Theory (G. Chartrand, M. Jacobson eds.) Congressus Numerantium 116 (1996) 193-230.

E. Prisner, Bicliques in graphs II: Recognizing $k$-path graphs and underlying graphs of line digraphs, Proceedings WG97, LNCS (1997)

E. Prisner, Intersection multigraphs of uniform hypergraphs, Graphs and Comb. 14 (1998) 363-375

E. Prisner, Generalized octahedra and cliques in intersection graphs of uniform hypergraphs, to appear in Discrete Math.

E. Prisner, The role of clique multigraphs in intersection graph theory, preprint 1998.

E. Prisner, Recognizing random intersection graphs, preprint 1998.

E. Prisner, A note on intersection graphs of dual hypergraphs, preprint 1999.

E. Prisner, The recognition problem for line bigraphs, preprint 1999.

S. Poljak, V. Rödl, D. Turzik, Complexity of representation of graphs by set systems, Discrete Appl. Math. 3 (1981) 301-312.

N.D. Roussopoulos, A max {m,n} algorithm for determining the graph H from its line graph G, Informat. Process. Letters 2 (1973) 108-112.

A. Raychaudhuri, On powers of interval and unit interval graphs, Congressus Numerantium 59 (1987) 235-242.

A. Raychaudhuri, On powers of strongly chordal and circular arc graphs, Ars Comb. 34 (1992) 147-160.

F.S. Roberts, J.H. Spencer, A characterization of clique graphs, J. Combin. Th. B 10 (1971) 102-108.

A.C.M. vanRooij, H.S. Wilf, The interchange graph of a finite graph, Acta Math. Acad. Sc. Hung. 16 (1965) 263-269.

E.R. Scheinerman, Characterizing intersection classes of graphs, Discrete Math. 55 (1985) 185-193.

P. Scheffler, What graphs have bounded tree-width? Rostocker Math. Kolloq. 41 (1990) 31-38.

G. Steiner, The recognition of indifference digraphs and generalized semiorders, J. Graph Th. 21 (1996) 235-241.

L. Szwarcfiter and C. F. Bornstein, Clique graphs of chordal and path graphs, SIAM J. Discrete Math. 7 (1994) 331-336.

M. Sen, S. Das, A.B. Roy, D.B. West, Interval digraphs, an analogue of interval graphs, J. Graph Th. 13 (1989).

S. Tsukiyama, M. Ide, M. Aiyoshi, I. Shirawaka, A new algorithm for generating all the independent sets, SIAM J. Computing 6 (1977) 505-517.

H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150-168.

G. Wegner, Eigenschaften der Nerven homologisch-einfacher Familien im Rn, Dissertation Göttingen 1967.

M. Yannakakis, The complexity of the partial order dimension problem, SIAM J. Alg. Disc. Meth. 3 (1981) 351-358.












Erich Prisner
made on January 12, 1999