Note: The references are not ordered alphabetically!
1200 |
McMorris, F.R.; Wang, Chi; Zhang, Peisen On probe interval graphs. Discrete Appl. Math. 88, No.1-3, 315-324 (1998). ZMath 0918.05087 |
1201 |
Golumbic, Martin Charles; Lipshteyn, Marina On the hierarchy of interval, probe and tolerance graphs. Congr. Numerantium 153, 97-106 (2001). ZMath 0995.05104 |
1202 |
M.C. Golumbic, M. Lipshteyn Chordal probe graphs Discrete Appl. Math. 143 No.1-3 221-237 (2004) ZMath 0211.8340 |
1203 |
D. Sumner Critical concepts in domination Discrete Math. 96 (1991) 75-80 ZMath 0725.05049 |
1204 |
I.E. Zverovich, V.E. Zverovich A characterization of domination perfect graphs. J. Graph Theory 15 (1991) 109-114 ZMath 0741.05074 |
1205 |
Prisner, Erich Graph dynamics. Pitman Research Notes in Mathematics Series. 338 (1995) ZMath 0848.05001 |
1206 |
Cockayne, E.J.; Hedetniemi, S.T.; Miller, D.J Properties of hereditary hypergraphs and middle graphs Can. Math. Bull. 21, 461-468 (1978) ZMath 0393.05044 |
1207 |
Hedetniemi, S.T.; Laskar, R.; Pfaff, J Irredundance in graphs: A survey. Combinatorics, graph theory and computing, Proc. 16th Southeast. Conf., Boca Raton/Fla. 1985, Congr. Numerantium 48, 183-193 (1985) ZMath 0647.05060 |
1208 |
R. Laskar, J. Pfaff Domination and irredundance in graphs Tech Report 434, Dept. Mathematical Sciences, Clemson University 1983 |
1209 |
M.C. Golumbic Future directions on tolerance graphs Congressus Numerantium 139 (1999) 213-220 ZMath 0960.05099 |
1210 |
Golumbic, Martin Charles; Lipshteyn, Marina On the hierarchy of interval, probe and tolerance graphs. Congr. Numerantium 153, 97-106 (2001) ZMath 0995.05104 |
1211 |
Deogun, Jitender S.; Kratsch, Dieter Dominating pair graphs. SIAM J. Discrete Math. 15, No.3, 353-366 (2002) ZMath 1007.05085 |
1212 | Result by M. Bertschi |
1213 |
Hagauer, Johann Skeletons, recognition algorithm and distance matrix of quasi-median graphs. Int. J. Comput. Math. 55, No.3-4, 155-171 (1995) ZMath 0845.68055 |
1214 |
D. Kratsch, J. Spinrad Between O(nm) and O(n^alpha) Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, Baltimore, MD, USA, January 12-14, 2003. New York, NY: Association for Computing Machinery. 709-716 (2003). [ISBN 0-89871-538-5/pbk] ZMath 02079402 |
1215 |
S.D. Nikolopoulos, L. Palios Recognizing bipolarizable and P4-simplicial graphs WG 2003, LNCS 2880 (2003) 358-369 |
1216 |
S. De Agostino, R. Petreschi, A. Sterbini An O(n^3) recognition algorithm for bithreshold graphs Algorithmica 17 (1997) 416-425 ZMath 0869.68068 |
1217 |
V.B. Le, J. Spinrad Consequences of an algorithm for bridged graphs. manuscript, 1999 ZMath 1041.05072 |
1218 |
Elaine M. Eschen, Julie L. Johnson, Jeremy P. Spinrad, R. Sritharan Recognition of some perfectly orderable graph classes. Discrete Appl. Math. 128, No.2-3, 355-373 (2003). [ISSN 0166-218X] ZMath 1019.68075 |
1219 |
R. McConnell Linear-time recognition of circular-arc graphs. Algorithmica 37 (2003) 93-47 ZMath 02055149 |
1220 |
F. Roussel, I. Rusu A linear algorithm to color $i$-triangulated graphs. Research Report RR 98-10, LIFO Universit\'e d'Orleans, France (1998). Or: Inf. Process. Lett. 70, No.2, 57-62 (1999). [ISSN 0020-0190] ZMath 0990.05113 |
1221 |
W. Imrich, S. Klavzar Product graphs Wiley, 2000 ZMath |
1222 |
E.M. Eschen, J.L. Johnson, J.P. Spinrad, R. Sritharan Recognition of some perfectly orderable graph classes Discrete Appl. Math. 128 (2003) 355-373 ZMath 1019.68075 |
1223 |
S.D. Nikolopoulos, L. Palios On the recognition of P_4-comparability graphs WG 2002, LNCS 2573 (2002) 355-366 ZMath 1022.68602 |
1224 |
M. Habib, C. Paul, L. Viennot Linear time recognition of P_4-indifference graphs DMTCS 4 (2001) 173-178 ZMath 0981.05092 |
1225 |
R. Rizzi On the recognition of P4-indifferent graphs Discrete Math. 239 (2001) 161-169 ZMath 0979.05096 |
1226 |
M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vuskovic Cleaning for Bergeness manuscript 2003 |
1227 |
M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vuskovic Recognizing Berge graphs manuscript 2003 |
1228 |
M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vuskovic A polynomial algorithm for recognizing Berge graphs manuscript 2003 |
1229 |
A. Sterbini, T. Raschle An O(n^3) algorithm for recognizing threshold dimension 2 graphs Inform. Proc. Lett. 67 (1998) 255-259 |
1230 |
S.D. Nikolopoulos, L. Palios Hole and antihole detection in graphs Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms (2004) 850-859 |
1231 |
D. Gernert Forbidden and unavoidable subgraphs Ars Combinatorica 27 (1989) 165-176 ZMath 0673.05047 |
1232 |
Li Sheng Cycle free probe interval graphs Congr. Numer. 140 33-42 (1999) ZMath 0960.05085 |
1233 | Let G be claw-free and \alpha(G)>=3. If G has an odd anti-hole then G has an odd-hole . |
1234 |
M. Skowronska, M.M. Syslo An algorithm to recognize a middle graph Discrete Appl. Math. 7 (1984) 201-208 ZMath 0528.05049 |
1235 |
J. Akiyama, T. Hamada, I. Yoshimura On characterizations of middle graphs TRU Mathematics 11 (1975) 35-39 ZMath 0333.05124 |
1236 |
T. Hamada, I. Yoshimura Traversability and connectivity of the middle graph of a graph Discrete Math. 14 (1976) 247-255 ZMath 0319.05122 |
1237 |
J. Kratochvil, M. Pergel Two results on intersection graphs of polygons Proceedings of Graph Drawing 2003, LNCS 2912 59-70 (2004) |
1238 |
R.S.Sankaranarayana, L.K.Stewart Complexity results for well-covered graphs Networks 22 (1992) 247-262 ZMath 0780.90104 |
1239 |
V. Chvatal, P.J. Slater A note on well-covered graphs Ann. Discrete Math. 55 (1993) 179-182 ZMath 0801.68119 |
1240 |
B. Randerath, I. Schiermeyer Vertex colouring and forbidden subgraphs - a survey Graphs and Combinatorics 20 (2004) 1-40 |
1241 |
B. Randerath The Vizing bound for the chromatic number based on forbidden pairs Ph.D. Thesis RWTH Aachen, Shaker Verlag (1998) |
1242 |
B. Randerath, I. Schiermeyer, M. Tewes Three-colourability and forbidden subgraphs II: polynomial algorithms Discrete Math. 251 137-212 (2002) ZMath 0999.05042 |
1243 |
B. Randerath, I. Schiermeyer 3-colorability in P for P_6-free graphs Discrete Appl. Math. 136 299-313 (2004) ZMath 1035.05042 |
1244 |
J. Bang-Jensen, J. Huang, A. Yeo Convex-round and concave-round graphs SIAM J. Discrete Math. Vol.13 No.2 179-193 (2000) ZMath 0941.05056 |
1245 |
Y. Daniel Liang, N. Blum Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits Inform. Proc. Letters Vol.56 No.4 215-219 (1995) ZMath 0875.68698 |
1246 |
V. Alekseev, P. Lozin, R. Mosca Maximum independent set problem and P_5-free graphs Manuscript 2004 |
1247 |
N. Nishimura, P. Ragde, D.M. Thilikos On graph powers for leaf-labeled trees J. Algorithms 42 No.1 69-108 (2002) ZMath 0990.68100 |
1248 |
M. Dom, J. Guo, F. Hueffner, R. Niedermeyer Error compensation in leaf root problems Presentation at Schloss Dagstuhl conference 04221 (2004) |
1249 |
Hell, Pavol; Klein, Sulamita; Protti, Fábio; Tito, Loana On generalized split graphs Proceedings of the Brazilian symposium on graphs, algorithms and combinatorics, Fortaleza, Ceara, Brazil, March 17-19, 2001. Extended abstracts. Electron. Notes Discrete Math. 7 (2001) ZMath 0981.05076 |
1250 |
J.R.S. Blair, S.S. Ravi TR-matching for chordal graphs Proceedings twentyseventh conference on communication, control and computing 72--81 (1989) |
1251 |
J.R.S. Blair, S.S. Ravi On finding maxium transmitter-receiver matchings in chordal networks Networks, to appear. |
1252 |
J.R.S. Blair The efficiency of AC graphs Discrete Appl. Math. 44 119-138 (1993) ZMath 0788.68106 |
1253 |
J.R.S. Blair, S.M. Hedetniemi, S.T. Hedetniemi Linear-time algorithms for domination in thick trees Manuscript, 2000 |
1254 |
A.V. Gagarin, Yu. M. Metelsky Characterization of (1,2)-polar graphs (in Russian) Vestsi Nats. Akad. Navuk Belarusi Ser. Fiz.-Mat. Navuk No.3 107-112 (1999) |
1255 |
I.E. Zverovich Bithreshold graphs (in Russian) Vestn. Beloruss. Gos. Univ., Ser. 1, Fiz. Mat. Inform. 2000, No.2, 78-80, 96 (2000) ZMath 0974.05067 |
1256 |
I.E. Zverovich Perfect connected-dominant graphs Discuss. Math., Graph Theory 23 No.1 159-162 (2003) ZMath 1037.05038 |
1257 |
I.E. Zverovich The domination number of (K_p,P_5)-free graphs Australas. J. Comb. 27 95-100 (2003) ZMath 1022.05060 |
1258 |
Hoàng, Chín T.; Maffray, Frédéric; Olariu, Stephan; Preissmann, Myriam A charming class of perfectly orderable graphs Discrete Math. 102, No.1, 67-74 (1992) ZMath 0776.05091 |
1259 |
A. Hertz Slim graphs Graphs Combin. 5 no.2 149-157 (1989) ZMath 0677.05065 |
1260 |
C.T. Hoang, F. Maffray On slim graphs, even pairs and star-cutsets Discrete Math. 105 No.1-3 93--102 (1992) ZMath 0769.05087 |
1261 |
L. Volkmann, V.E. Zverovich Proof of a conjecture on irredundance perfect graphs J. Graph Th. 41 No.4 292-306 (2002) ZMath 1015.05068 |
1262 |
I.E. Zverovich Near-complete multipartite graphs and forbidden induced subgraphs Discrete Math. 207 No.1-3 257-262 (1999) ZMath 0943.05036 |
1263 |
G. Gutin, V.E. Zverovich Upper domination and upper irredundance perfect graphs Discrete Math. 190 No.1-3 239-256 (1999) ZMath 0956.05077 |
1264 |
M.C. Golumbic, R.C. Laskar Irredundancy in circular arc graphs Discrete Appl. Math. 44 No.1-3 79-89 (1993) ZMath 0783.05059 |
1265 |
I.E. Zverovich, V.E. Zverovich A semi-induced subgraph characterization of upper domination perfect graphs J. Graph Th. 31 No.1 29-49 (1999) ZMath 0920.05060 |
1266 |
Jacobson, Michael S.; Peters, Ken Chordal graphs and upper irredundance, upper domination and independence Discrete Math. 86, No.1-3, 59-69 (1990) ZMath 0744.05063 |
1267 |
D. Rautenbach, V.E. Zverovich Perfect graphs of strong domination and independent strong domination Discrete Math. 226 No.1-3 297-311 (2001) ZMath 0972.05037 |
1268 |
Guruswami, Venkatesan; Rangan, C.Pandu Algorithmic aspects of clique-transversal and clique-independent sets Discrete Appl. Math. 100, No.3, 183-202 (2000) ZMath 948.68135 Note that the claim in 5. Conclusions that odd anti-hole s are not clique-perfect is incorrect for odd anti-hole s of length 3k+9 (k >= 0). See also
[1270]
(Communicated by Flavia Bonomo).
G. Duran, M. Chih Lin, J.L. Szwarcfiter
On clique-transversals and clique-independent sets Ann. Oper. Res. 116 71-77 (2002) |
1269 |
V. Balachandhran, P. Nagavamsi, C. Pandu Ragan Clique transversal and clique independence on comparability graphs Inf. Proc. Letters 58 181-184 (1996) |
1270 |
G. Duran, M. Chih Lin, J.L. Szwarcfiter On clique-transversals and clique-independent sets Ann. Oper. Res. 116 71-77 (2002) |
1271 |
A. Berry, M.C. Golumbic, M. Lipshteyn Recognizing and triangulating chordal probe graphs Research Report LIMOS/RR-03-08 (2003) |
1272 |
A. Hertz Slender graphs J. Comb. Theory, Ser. B 47 No.2 231-236 (1989) ZMath 0634.05060 |
1273 |
A. Hertz Skeletal graphs - a new class of perfect graphs Discrete Math. 78 No.3 291-296 (1989) ZMath 0691.05047 |
1274 |
C.M.H. de Figueiredo, K. Vuskovic Recognition of quasi-Meyniel graphs Discrete Appl. Math. 113 255-260 (2001) ZMath 1001.68089 |
1275 |
Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vuskovic, Kristina Even-hole-free graphs. I: Decomposition theorem J. Graph Theory 39, No.1, 6-49 (2002) ZMath 1005.05034 |
1276 |
Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vuskovic, Kristina Even-hole-free graphs. II: Recognition algorithm J. Graph Theory 40, No.4, 238-266 (2002) ZMath 1003.05095 |
1277 |
M. Chudnovsky, K-i. Kawarabayashi, P. Seymour Detecting even holes J. Graph Theory 48, No.2, 85--111 (2005) doi 10.1002/jgt.20040 |
1278 |
C.M.H. de Figueiredo, F. Maffray Optimizing bull-free perfect graphs SIAM J. Discrete Math. Vol.18 No.2 226-240 (2004) |
1279 |
Yu. Metelsky, R. Tyshkevich Line graphs of Helly hypergraphs SIAM J. Discrete Math. Vol.16 No.3 438-448 (2003) ZMath 1029.05107 |
1280 |
R.M. McConnell, J.P. Spinrad Construction of probe interval models Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02) 866-875 (2002) ZMath 0211.9749 |
1281 |
C.T. Hoand, R. Sritharan Finding houses and holes in graphs Theoret. Comput. Sci. 259 233-244 (2001) |
1282 |
N. Przulj, D.G. Corneil 2-tree probe interval graphs have a large obstruction set Accepted for Discrete Appl.Math. |
1283 |
P. Bose, A. Dean, J. Hutchinson, T. Shermer On rectangle visibility graphs Proceedings of Graph Drawing '96, LNCS 1190, 25-35 (1997) |
1284 |
Duchet, P.; Hamidoune, Y.; Las Vergnas, M.; Meyniel, H. Representing a planar graph by vertical lines joining different levels Discrete Math. 46 319-321 (1983) ZMath 0516.05023 |
1285 |
F. Luccio, S. Mazzone, C.K. Wong A note on visibility graphs Discrete Math. 64 209-219 (1987) |
1286 |
R. Tamassia, I.G. Tollis A unified approach to visibility representations of planar graphs Dicrete Comput. Geom. 1 321-341 (1986) ZMath 0607.05026 |
1287 |
S.K. Wismath Bar-representable visibility graphs and a related network flow problem PhD Thesis, Dept. of computer science, University of British Columbia (1989) |
1289 |
P. Horak, L. Niepel A short proof of a linear arboricity theorem for cubic graphs Act Math. Univ. Comenianae No.40-41, 275-278 (1982) ZMath 0548.05057 |
1290 |
V. Lozin, R. Mosca Independent sets and extensions of 2K_2-free graphs Discrete Appl. Math. 146 74-80 (2005) |
1291 |
T.C. Shermer On rectangle visibility graphs III. External visibility and complexity Proc. of the 8th Canadian Conference on Computation Geometry CCCG'96 234-239 (1996) |
1292 |
Przulj, Natasa; Corneil, Derek G.; Köhler, Ekkehard Hereditary dominating pair graphs. Discrete Appl. Math. 134, No.1-3, 239-261 (2004) ZMath 1032.05116 |
1293 |
Schaefer, Marcus; Stefankovic, Daniel Decidability of string graphs J. Comput. Syst. Sci. 68, No.2, 319-334 (2004) ZMath 02117376 |
1294 |
G.J. Chang, T. Kloks, S.L. Peng Probe interval bigraphs Electronic Notes in Discrete Math. 19 195-201 (2005) |
1295 |
G.J. Chang, A.J.J. Kloks, J. Liu, S.L. Peng The PIGs full monty - A floor show of minimal separators To appear at STACS 2005, LNCS 3404 |
1296 |
Conforti, Michele; Cornuéjols, Gérard; Vuskovic, Kristina Square-free perfect graphs J. Comb. Theory, Ser. B 90, No.2, 257-307 (2004) ZMath 1033.05047 |
1297 |
I.E. Zverovich, V.E. Zverovich Basic perfect graphs and their extensions Discrete Math. 293 (2005) 291-311 |
1298 |
E. Prisner Hereditary clique-helly graphs J. Comb. Math. Comb. Comput 14 216-220 (1993) ZMath 0794.05113 |
1299 |
W.D. Wallis, G-H Zhang On maximal clique irreducible graphs J. Comb. Math. Comb. Comput 8 187-193 (1990) ZMath 0735.05052 |