Note: The references are not ordered alphabetically!
1 |
J. Abello, O. Egecioglu Visibility graphs of staircase polygons with uniform step length {\sl International Journal of Computational Geometry Applications} 3 1993 27--37 ZMath 0771.68098 |
2 |
J. Abello, O. Egecioglu, K. Kumar Visibility graphs of staircase polygons and the weak Bruhat order I: from visibility graphs to maximal chains Discrete Computational Geometry 14 1995 331--358 ZMath 0835.05065 |
3 |
J. Abello, H. Lin, S. Pisupati On visibility graphs of simple polygons Congressus Numerantium 90 119--128 1992 ZMath 0786.05077 |
4 |
D. Achlioptas The complexity of $G$--free colourability Discrete Math. 165/166 21--30 1997 ZMath 0904.05030 |
5 |
R. Aharoni, R. Holzman Fractional kernels in digraphs J. Comb. Theory (B) 73 1--6 1998 ZMath 0904.05036 |
6 |
A.V. Aho, J.E. Hopcroft, J.D. Ullman The design and analysis of computer algorithms Addison--Wesley, Reading, Mass. 1974 ZMath 0326.68005 |
7 |
M. Aigner, E. Triesch Reconstructing a graph from its neighbourhood list Comb. Prob. Comp. 2 1993 103--113 ZMath 0792.05104 |
8 |
M. Aigner, E. Triesch Realizability and uniqueness in graphs Discrete Math. 136 1994 3--20 ZMath 0817.05048 |
9 |
H. Ait Haddadene, S. Gravier On weakly diamond--free Berge graphs Discrete Math. 159 1996 237--240 ZMath 0859.05045 |
10 |
H. Ait Haddadene, F. Maffray Coloring perfect degenerate graphs Discrete Math. 163 1997 211--215 ZMath 0870.05020 |
11 |
M. Ajtai, J. Koml\'os, E. Szemer\'edi Sorting in clogn parallel steps Combinatorica 3 1983 1--19 ZMath 0523.68048 |
12 |
J. Akiyama, V. Chv\'atal Packing graphs perfectly Discrete Math. 85 1990 247--255 ZMath 0723.05092 |
13 |
M.O. Albertson, K.L. Collins Duality and perfection for edges in cliques J. Comb. Theory (B) 36 1984 298--309 ZMath 0527.05032 |
14 |
N. Alon Eigenvalues and expanders Combinatorica 6 1986 83--96 ZMath 0661.05053 |
15 |
N. Alon, N. Kahale A spectral technique for coloring random 3--colorable graphs SIAM J. Computing 26 1733--1748 1997 ZMath 0884.05042 |
16 |
N. Alon, N. Kahale Approximating the independence number via the $\vartheta$--function Math. Programming 80 253--264 1998 ZMath 0895.90169 |
17 |
N. Alon, P. Seymour, R. Thomas A separator theorem for graphs with an excluded minor and its applications Proceedings of the 22nd Ann. ACM Sympos. on Theory of Comp. 1990 293--299 |
18 |
R. Anand, H. Balakrishnan, C. Pandu Rangan Treewidth of distance--hereditary graphs manuscript %??? 1994 |
19 |
T. Andreae On superperfect noncomparability graphs J. Graph Theory 9 1985 523--532 ZMath 0664.05051 |
20 |
T. Andreae On the unit interval number of a graph Discrete Appl. Math. 22 (1988/89) 0 1--7 ZMath 0673.05084 |
21 |
T. Andreae Some results on visibility graphs Discrete Appl. Math. 40 1992 5--17 ZMath 0781.05013 |
22 |
T. Andreae, U. Hennig, A. Parra On a problem concerning tolerance graphs Discrete Appl. Math. 46 1993 73--78 ZMath 0786.05084 |
23 |
R.P. Anstee, M. Farber Characterizations of totally balanced matrices J. Algorithms 5 1984 215--230 ZMath 0551.05026 |
24 |
R.P. Anstee, M. Farber On bridged graphs and cop--win graphs J. Comb. Theory (B) 44 1988 22--28 ZMath 0654.05049 |
25 |
S. Arnborg, D.G. Corneil, A. Proskurowski Complexity of finding embeddings in a $k$--tree SIAM J. Alg. Discr. Meth. 8 1987 277--284 ZMath 0611.05022 |
26 |
S. Arnborg, B. Courcelle, A. Proskurowski, D. Seese An algebraic theory of graph reduction J. ACM 40 1993 1134--1164 ZMath 0795.68156 |
27 |
S. Arnborg, J. Lagergren, D. Seese Easy Problems for tree--decomposable graphs J. Algorithms 12 1991 308--340 ZMath 0734.68073 |
28 |
S. Arnborg, A. Proskurowski Linear time algorithms for \NP--hard problems restricted to partial $k$--trees Discrete Appl. Math. 23 1989 11--24 ZMath 0666.68067 |
29 |
S. Arnborg, A. Proskurowski Characterization and recognition of partial 3-trees SIAM J. Alg. Discr. Meth. 7 1986 305--314 ZMath 0597.05027 |
30 |
S. Arnborg, A. Proskurowski, D.G. Corneil Forbidden minors characterization of partial 3--trees Discrete Math. 80 1990 1--19 ZMath 0701.05016 |
31 |
T. Asano Difficulty of the maximum independent set problem on intersection graphs of geometric objects Proceedings of the Sixth Internat. Conf. on the Theory and Applicationsof Graphs, Western Michigan University 1988, {\sc Y. Alavi, G. Chartrand,O.R. Oellerman, A.J. Schwenk}, eds.J. Wiley, New York 1988 ZMath 0841.68082 |
32 |
M.D. Atkinson On computing the number of linear extensions of a tree Order 7 1990 23--25 ZMath 0793.06002 |
33 |
F. Aurenhammer, J. Hagauer, W. Imrich Cartesian graph factorization at logarithmic cost per edge Comput. Complexity 2 1992 331--349 ZMath 0770.68064 |
34 |
G. Ausiello, A. D'Atri, M. Moscarini Chordality properties on graphs and minimal conceptual connections in semantic data models J. Comput. Syst. Sciences 33 1986 179--202 ZMath 0625.68076 |
35 |
L. Auslander, S. Parter On embedding graphs in the sphere J. Math. Mech. 10 1961 517--523 ZMath 0101.16704 |
36 |
L. Babel On the $P_4$--structure of graphs Habilitation Thesis, TU M\"unchen 1997 |
37 |
L. Babel, A. Brandst\"adt, V.B. Le Recognizing the $P_4$--structure of bipartite graphs submitted for publication 1998 ZMath 0931.68074 |
38 |
L. Babel, S. Olariu On the isomorphism of graphs with few $P_4$s {\sc M. Nagl}, ed., 21st Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. WG'95, Lecture Notes in Comp. Sci. 1017 1995 24--36 |
39 |
L. Babel, S. Olariu A new characterization of $P_4$--connected graphs {\sc G. Ausiello, A. Marchetti--Spaccamela}, eds., 22nd Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. WG'96,Lecture Notes in Comp. Sci. 1197 1996 17--30 |
40 |
G. Bacs\'o, E. Boros, V. Gurvich, F. Maffray, M. Preissmann On minimally imperfect graphs with circular symmetry RUTCOR Research Report, Rutgers University, New Brunswick NJ, RRR 22--94 1994 http://rutcor.rutgers.edu/pub/rrr/reports94/21.ps |
41 |
G. Bacs\'o, Z. Tuza A characterization of graphs without long induced paths J. Graph Theory 1990 455--464 ZMath 0717.05044 |
42 |
G. Bacs\'o, Z. Tuza Dominating cliques in $P_5$--free graphs Periodica Math. Hungaria 21 1990 303--308 ZMath 0746.05065 |
43 |
G. Bacs\'o, Z. Tuza Domination properties and induced subgraphs Discrete Math. 111 1993 37--40 ZMath 0784.05030 |
44 |
B.S. Baker Approximation algorithms for \NP--complete problems on planar graphs Proceedings 24th Ann. IEEE Conf. on Foundat. of Comp. Sci. 1983 265--273 ZMath 0807.68067 |
45 |
K.A. Baker, P.C. Fishburn, F.S. Roberts Partial orders of dimension 2 Networks 1971 11--28 ZMath 0247.06002 |
46 |
R. Balakrishnan, P. Paulraja Powers of chordal graphs J. Austral. Math. Soc. Ser. A 35 1983 211--217 ZMath 0526.05055 |
47 |
H.--J. Bandelt Characterizing median graphs manuscript, 1987 0 |
48 |
H.--J. Bandelt Hereditary modular graphs Combinatorica 8 1988 149--157 ZMath 0659.05076 |
49 |
H.--J. Bandelt Graphs with intrinsic $S_3$ convexities J. Graph Theory 13 1989 215--228 ZMath 0671.05049 |
50 |
H.--J. Bandelt Neighbourhood--Helly Powers Abhandl. Math. Seminar Univ. Hamburg 1992 |
51 |
H.--J. Bandelt Graphs with edge--preserving majority functions Discrete Math. 103 1992 1--5 ZMath 0766.05024 |
52 |
H.--J. Bandelt, V.D. Chepoi A Helly theorem in weakly modular space Discrete Math. 160 1996 25--39 ZMath 0864.05049 |
53 |
H.--J. Bandelt, A. D\"ahlmann, H. Sch\"utte Absolute retracts of bipartite graphs Discrete Appl. Math. 16 1987 191--215 ZMath 0614.05046 |
54 |
H.--J. Bandelt, M. Farber, P. Hell Absolute reflexive retracts and absolute bipartite retracts Discrete Appl. Math. 44 1993 9--20 ZMath 0795.05133 |
55 |
H.--J. Bandelt, A. Henkmann, F. Nicolai Powers of distance--hereditary graphs Discrete Math. 145 1995 37--60 ZMath 0838.05045 |
56 |
H.--J. Bandelt, H.M. Mulder Interval--regular graphs of diameter two Discrete Math. 50 1984 117--134 ZMath 0544.05049 |
57 |
H.--J. Bandelt, H.M. Mulder Distance--hereditary graphs J. Comb. Theory (B) 41 1986 182--208 ZMath 0605.05024 |
58 |
H.--J. Bandelt, H.M. Mulder Pseudo--modular graphs Discrete Math. 62 1986 245--260 ZMath 0606.05053 |
59 |
H.--J. Bandelt, H.M. Mulder Three interval conditions for graphs Ars Combinatoria 29 1990 213--223 ZMath 0743.05054 |
60 |
H.--J. Bandelt, H.M. Mulder Metric characterization of parity graphs Discrete Math. 91 1991 221--230 ZMath 0753.05057 |
61 |
H.--J. Bandelt, H.M. Mulder Pseudo--median graphs: decomposition via amalgamation and Cartesian multiplication Discrete Math. 94 1991 161--180 ZMath 0743.05055 |
62 |
H.--J. Bandelt, H.M. Mulder Cartesian factorization of interval--regular graphs having no long isometric odd cycles in: {\sl Graph Theory, Combinatorics, and Applications}, Vol. 1,{\sc Y. Alavi, G. Chartrand, R. Oellermann, A.J. Schwenk}, eds.,J. Wiley, New York 1991 55--75 ZMath 0840.05074 |
63 |
H.-J. Bandelt, H.M. Mulder, E. Wilkeit Quasi--median graphs and algebras J. Graph Theory 18 1994 681--703 ZMath 0810.05057 |
64 |
H.--J. Bandelt, E. Pesch Dismantling absolute retracts of reflexive graphs European J. Combin. 10 1989 211--220 ZMath 0674.05065 |
65 |
H.--J. Bandelt, E. Pesch Efficient characterizations of $n$--chromatic absolute retracts J. Comb. Theory (B) 53 1991 5--31 ZMath 0751.05036 |
66 |
H.--J. Bandelt, E. Prisner Clique graphs and Helly graphs J. Comb. Theory (B) 51 1991 34--45 ZMath 0726.05060 |
67 |
H.--J. Bandelt, M. van de Vel Superextensions and the depth of median graphs J. Comb. Theory (A) 57 1991 187--202 ZMath 0756.05091 |
68 |
J. Bang--Jensen, P. Hell On chordal proper circular arc graphs Discrete Math. 128 1994 395--398 ZMath 0796.05080 There is an omission in the hypothesis of Theorem 1 (p. 396): "Theorem 1. Let G be a graph which contains no induced claw, net, four cycle, or five-cycle. If G contains the tent as an induced subgraph, then G is a multiple of a tent." They omit to ask the graph G to be connected, but they use that fact implicitly in the first paragraph and explicitly in the beginning of the second paragraph "Since G is connected..." (sic). S3 ∪ K1 is an example of a graph that meets the hypothesis of Theorem 1, but that doesn't satisfy the thesis. (It could happen because S_3\cup K_1 is not connected.) If you add the hypothesis "G is connected" to Theorem 1 then the proof becomes correct. Accordingly the hypothesis "G is connected" should be added also to the Corollary 3, which should say: "A chordal connected (!) graph G is a proper circular arc graph if and only if it is claw-free and net-free." The correct statements are: 1) "chordal\cap proper circular arc\cap connected" is equivalent to "(C_{n+4},claw,net)-free". 2) "chordal\cap proper circular arc" is equivalent to "(C_{n+4},claw,net,S_3\cup K_1)-free". which are Teorema 2.4 and Corolario 2.2, respectively, of
[1328]
.
(courtesy of Martin Dario Safe)G.A. Duran
Sobre grafos intersección de arcos y cuerdas en un círculo Doctoral dissertation, Universidad de Buenos Aires, 2000. (In Spanish.) |
69 |
V. Barr\'e, J.--L. Fouquet On minimal imperfect graphs without induced $P_5$ manuscript, Universit\'e du Maine, Le Mans, 1996 0 ZMath 0936.05045 |
70 |
J.--P. Barth\'elemy, J. Constantin Median graphs, parallelism and posets Discrete Math. 111 1993 49--63 ZMath 0787.05027 |
71 |
D. Bauer, H.J. Broersma, H.J. Veldman Not every 2--tough graph is Hamiltonian Memorandum No. 1400, Universiteit Twente 1997 ZMath 0934.05083 |
72 |
D. Bauer, S.L. Hakimi, E. Schmeichel Recognizing tough graphs is \NP--hard Discrete Appl. Math. 28 1990 191--195 ZMath 0706.68052 |
73 |
S. Baumann A linear algorithm for the homogeneous decomposition of graphs Tech. Report M--9615, Institut f\"ur Mathematik, TU M\"unchen 1996 |
74 |
C. Beeri, R. Fagin, D. Maier, A. Mendelzon, J.A. Ullman, M. Yannakakis Properties of acyclic database schemas 13th Ann. ACM Sympos. on Theory of Comp. 1981 355--362 |
75 |
C. Beeri, R. Fagin, D. Maier, M. Yannakakis On the desirability of acyclic database schemes J. ACM 30 1983 479--513 ZMath 0624.68087 |
76 |
H. Behrendt, A. Brandst\"adt Domination and the use of maximum neighbourhoods Schriftenreihe des Fachbereichs Mathematik der Universit\"at Duisburg SM-DU-204 1992 |
77 |
L.W. Beineke On derived graphs and digraphs Beitr. Graphentheorie, Int. Kolloquium Manebach (DDR) 1967, 17-23 (1968). ZMath 0179.29204 |
78 |
L.W. Beineke Characterization of derived graphs J. Comb. Theory 9 1970 129--135 ZMath 0202.55702 |
79 |
L.W. Beineke, R.E. Pippert The enumeration of labelled 2--trees Notices Amer. Math. Soc. 15 384 1968 |
80 |
L.W. Beineke, R.E. Pippert The number of labeled k-dimensional trees J. Comb. Theory 6, 200-205 (1969). ZMath 0175.20904 |
81 |
S. Bellantoni, I. Ben--Arroyo Hartman, T. Przytycka, S. Whitesides Grid intersection graphs and boxicity Discrete Math. 114 1993 41--49 ZMath 0784.05031 |
82 |
M. Bellare, O. Goldreich, S. Goldwasser Randomness in interactive proofs Ann. IEEE Conf. on Foundat. of Comp. Sci. 31 1990 563--572 ZMath 0802.68053 |
83 |
I. Ben--Arroyo Hartman, I. Newman, R. Ziv On grid intersection graphs Discrete Math. 87 1991 41--52 ZMath 0739.05081 |
84 |
C. Benzaken, Y. Crama, P. Duchet, P.L. Hammer, F. Maffray More characterizations of triangulated graphs J. Graph Theory 14 1990 413--422 ZMath 0721.05056 |
85 |
C. Benzaken, P.L. Hammer Linear separation of domination sets in graphs Annals of Discrete Math. 3 ({\sc B. Bollob\'as}, ed.) 1978 1--10 ZMath 0375.05043 |
86 |
C. Benzaken, P.L. Hammer, D. de Werra Threshold characterization of graphs with Dilworth number two J. Graph Theory 9 1985 245--267 ZMath 0583.05048Note that the drawing of G18 is incorrect. |
87 |
C. Benzaken, P.L. Hammer, D. de Werra Split graphs of Dilworth number 2 Discrete Math. 55 1985 123--128 ZMath 0573.05047 |
88 |
C. Berge Les probl\`emes de colorations en th\'eorie des graphes {\sl Publ. Inst. Stat. Univ. Paris, 9} 1960 123--160 ZMath 0103.16201 |
89 |
C. Berge F\"arbung von Graphen deren saemtliche bzw. deren ungeraden Kreise starr sind Wiss. Zeitschr. Martin-Luther-Univ. Halle-Wittenberg 114 1961 |
90 |
C. Berge Graphs and Hypergraphs North--Holland, Amsterdam 1985 ZMath 0213.25702 |
91 |
C. Berge Perfect graphs {\sl Studies in Graph Theory Part I} 1973 1--22 ZMath 0972.00015 |
92 |
C. Berge The $q$--perfect graphs. Part I: the case $q=2$ Hal\'asz, G. (ed.) et al., Sets, graphs and numbers. A birthday salute to Vera T. S\'os and Andr\'as Hajnal. Amsterdam: North-Holland Publishing Company. Colloq. Math. Soc. J\'anos Bolyai. 60, 67-75 (1992). [ISBN 0-444-98681-2/hbk] ZMath 0791.05036 |
93 |
C. Berge The $q$--perfect graphs. Part II Matematiche 47, No.2, 205-211 (1992). ZMath 0798.05021 |
94 |
C. Berge The $q$--perfect graphs RUTCOR Research Report, Rutgers University, New Brunswick NJ, RRR 23--92 1992 ZMath 0847.05053 |
95 |
C. Berge Motivations and history of some of my conjectures Discrete Math. 165/166 61--70 1997 ZMath 0873.05066 |
96 |
C. Berge, V. Chv\'atal (eds.) Topics on perfect graphs Annals of Discrete Math. 21 1984 ZMath 0546.00006 |
97 |
C. Berge, P. Duchet Probleme Seminaire du Lundi Tech. Report {\sl M.S.H. 54 Bd. Raspail 75006 Paris}, 1983 0 |
98 |
C. Berge, P. Duchet Strongly perfect graphs Annals of Discrete Math. 21 1984 57--61 ZMath 0558.05037 |
99 |
C. Berge, P. Duchet Perfect graphs and kernels Bull. Inst. Math. Acad. Sinica 16 1988 263--274 ZMath 0669.05037 |