Note: The references are not ordered alphabetically!

 1400 P. Gambette, S. Vialette On restrictions of balanced 2-interval graphs Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science WG'07, LNCS 4769, 55-65 (2007) 1401 V. Bafna, B.O. Narayanan, R. Ravi Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles) Discrete Appl. Math. 71 No.1 41-54 (1996) 1402 M. Chudnovsky, P. Seymour The structure of claw-free graphs Surveys in Combinatorics, London Math. Soc. Lecture Notes 327 153-172 (2005) 1403 The intersection of 2-subdivision and planar graphs is a proper subclass of grid intersection graphs, as large complete graphs are contained in the latter class, but not in the former. 1404 M.C. Lin, J.L. Szwarcfiter Characterizations and recognition of circular-arc graphs and subclasses: A survey Discrete Math. 309 No.18, 5618-5635 (2009) 1405 P. Hell, J. Huang Interval bigraphs and circular arc graphs J. Graph Theory 46 313-327 (2004) 1406 M.C. Lin, F. Soulignac, J.L. Szwarcfiter Proper Helly circular arc graphs Graph theoretic concepts in computer science. 33rd international workshop, WG '07 Jena, Germany. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 4769 248-257 (2007) Note that the claim that the proper Helly circularc arc graphs are precisely the clique graphs of Helly circular arc graphs contradicts [1483] M.C. Lin, F. Soulignac, J.L. Szwarcfiter The clique operator on circular-arc graphs Discrete Appl. Math. 158 (12) 1259-1267 (2010) , Th.7. 1407 M.K. Sen, S. Das, D.B. West Circular digraphs: A characterization J. of Graph Th. 13 581-592 (1989) 1408 A. Pecher, A.K. Wagler Clique and chromatic number of circular-perfect graphs Proceedings of ISCO 2010 - International Symposium on Combinatorial Optimization, Elec. Notes in Discrete Math 36 199-206 (2010) 1409 A. Pecher, A. Wagler, X. Zhu Three classes of minimal circular-imperfect graphs 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics GRACO'05 (2005) 1410 S. Coulonges, A. Pecher, A. Wagler Triangle-free strongly circular perfect graphs European conference on Combinatorics, Graph theory and Applications EuroComb 2005 1411 H.L. Bodlaender A partial k-arboretum of graphs with bounded treewidth Theor. Comp. Sci. 209 1-45 (1998) 1412 M. Syslo Characterisations of outerplanar graphs Discrete Math. 26 47-53 (1979) 1413 F.V. Fomin, P.A. Golovach, D. Lokshtanov, S. Saurabh Intractability of clique-width parametrizations SIAM J. Comput. 39 No.5 1941-1956 (2010) 1414 D.G. Corneil, U. Rotics On the relationship between clique-width and treewidth SIAM J. Comput. 34 825-847 (2005) 1415 W. Espelage, F. Gurski, E. Wanke Deciding clique-width for graphs of bounded tree-width J. Graph Algorithms Appl. 7 141-180 (2003) 1416 R. Garbe Tree-width and path-width of comparability graphs of interval orders 20th Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. WG'94, Lecture Notes in Comp. Sci. 903 (1995) 26-37 1417 H.L. Bodlaender, T. Kloks, D. Kratsch, H. Mueller Treewidth and minimum fill-in on d-trapezoid graphs J. Graph Algorithms Appl. 2 1-23 (1998) 1418 D. Meister Treewidth and minimum fill-in on permutation graphs in linear time Theoretical Comp. Sci. 411 No. 40-42 3685-3700 (2010) 1419 E. Dahlhaus Minimum fill-in and treewidth on graphs modularly decomposable into chordal graphs 24th Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. WG'98, Lecture Notes in Comp. Sci. 1517 (1998) 351-358 1420 H.J. Broersma, E. Dahlhaus, T. Kloks Algorithms for the treewidth and minimum fill-in of HHD-free graphs 23rd Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. WG'97, Lecture Notes in Comp. Sci. 1335 (1997) 109-117 1421 V. Bouchitte, I. Todinca Treewidth and minimum fill-in of weakly triangulated graphs Annual symposium on theoretical aspects of computer science STACS 99, Lecture Notes in Comp. Sci. 1563 (1999) 197-206 1422 L. Babel Triangulating graphs with few P4's Disc. Appl. Math. 89 45-57 (1998) 1423 A. Graef, M. Stumpf, G. Weissenfels On coloring unit disk graphs Algorithmica 20 277-293 (1998) 1424 C.T. Hoang Efficient algorithms for minimum weighted colouring of some classes of perfect graphs Discrete Appl. Math. 55 133-143 (1994) 1425 V. Guruswami, S. Khanna On the hardness of 4-coloring a 3-colorable graph Proceedings of hte 15th Annual IEEE Conference on Computational Complexity 188-197 (2000) 1426 F. Maffray, M. Preissmann On the NP-completeness of the k-colorability problem for triangle-free graphs Discrete Math. 162 No.1-3 313-317 (1996) 1427 C. Thomassen A short list color proof of Groetzsch's theorem J. Comb. Theory (B) 88 (2003) 189-192 1428 O.V. Borodin, A.N. Glebov, A. Raspaud, M.R. Salavatipour Planar graphs without cycles of length from 4 to 7 are 3-colorable J. Comb. Theory (B) 93 No.2 (2005) 303-311 1429 W.-L. Hsu Maximum weight clique algorithms for circular-arc graphs and circle graphs SIAM J. Computing 14 No.1 224-231 (1985) 1430 B. Bhattacharya, P. Hell, J. Huang A linear algorithm for maximum weight cliques in proper circular arc graphs SIAM J. Discrete Math. 9 No. 2 274-289 (1996) 1431 H. Broersma, P.A. Golovach, D. Paulusma, J. Song Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time Manuscript (2010) 1432 I. Holyer The NP-completeness of edge-coloring SIAM J. Computing 10 718-720 (1981) 1433 D. Kral, J. Kratochvil, Z. Tuza, G.J. Woeginger Complexity of coloring graphs without forbidden induced subgraphs Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 254-262 (2001) 1434 K. Dabrowski, V. Lozin, R. Raman, B. Ries Colouring vertices of triangle-free graphs Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2010, LNCS 6410, 184-195 (2010) 1435 A. Brandstaedt, K. Klembt, S. Mahfud P_6- and triangle-free graphs revisited: structure and bounded clique-width Discrete Math. Theor. Comput. Sci. 8 173-187 (2006) 1436 D. Schindl Some new hereditary classes where graph coloring remains NP-hard Discrete Math. 295 No.1 197-202 (2005) 1437 V. Lozin, J. Volz The clique-width of bipartite graphs in monogenic classes International J. of Foundations of Comp. Sci. 19 477-494 (2008) 1438 M.R. Garey, D.S. Johnson, G.L. Miller, C.H. Papadimitriou The complexity of coloring circular arcs and chords SIAM J. on Algebraic and Discrete Methods 1 No.2 216-227 (1980) 1439 J. Stacho 3-colouring of AT-free graphs in polynomial time 21st International Symposium on Algorithms and Computation ISAAC, Lecture Notes in Comp. Sci. LNCS 6507 144-155 (2010) 1440 M. Kochol Linear algorithm for 3-coloring of locally connected graphs 2nd International Workshop on Experimental and Efficient Algorithms WEA 2003, Lecture Notes in Comp. Sci. LNCS 2647 191-194 (2003) 1441 C.T. Hoang, M. Kaminski, V. Lozin, J. Sawada, X. Shu Deciding k-colorability of P_5-free graphs in polynomial time Algorithmica Vol.57 No.1 74-81 (2010) 1442 D.G. Corneil, E. Koehler, S. Olariu, L. Stewart Linear orderings of subfamilies of AT-free graphs SIAM J. Discrete Math. Vol.20 No.1 105-118 (2006) 1443 I.E. Zverovich A new kind of graph coloring J. of Algorithms Vol.58 No.2 118-133 (2006) 1444 Use a colour per direction. 1445 M. Chlebik, J. Chlebikova Approximation hardness of dominating set problems in bounded degree graphs Information and Computation Vol.206 p 1264-1275 (2008) 1446 By Brooks' theorem, a connected graph of maximum degree 3 is either biparite (and thus 2-colourable), or isomorphic to a K4 (and thus 4-colourable), or 3-colourable. 1447 A. Brandstaedt, V.V. Lozin, R. Mosca Independent sets of maximum weight in apple-free graphs SIAM J. Discrete Math. Vol.24 No.1 239-254 (2010) 1448 Put the centers of the disks on the same line. (P. Ochem) 1449 odd anti-hole s of size at least 7 are not planar (Communicated by P. Ochem): Every odd anti-hole of size at least 11 contains a K5 as an induced subgraph. For the complement of the cycle v1..v9, the subgraph induced by v1,v2,v4, v6,v9,v9 contains K3,3 as a partial subgraph. The complement of the cycle v1..v7 is homeomorphic to K3,3 by deletion of the edges v3v4, v4v5; contraction of the path v2v4v6 and finally deletion of the edges v1v2, v6v7. 1450 J. Kratochvil Geometric representations of graphs Course notes for the Graph Theory Course at UPC, Barcelona (2005) Available here. 1451 S.-L. Peng, M.-T. Ko, C.-W. Ho, T.-S. Hsu C.Y. Tang Graph searching on some subclasses of chordal graphs Algorithmica 27 395-426 (2000) 1452 R. Mosca Stable sets of maximum weight in (P_7, banner)-free graphs Discrete Math. 308 Issue 1 20-33 (2008) 1453 A. Bondy, G. Duran, M. Lin, J. Szwarcfiter Self-clique graphs and matrix permutations J. Graph Theory 44 178-192 (2003) 1454 F. Bonomo Self-clique Helly circular-arc graphs Discrete Math. 306 Issue 6 595-597 (2006) 1455 M. Pergel Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete Graph theoretic concepts in computer science. 33rd international workshop, WG '07 Jena, Germany. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 4769 238-247 (2007) 1456 J. Kratochvil, A. Kubena On intersection representations of co-planar graphs Discrete Math. 178 No.1-3 251-255 (1998) 1457 J. Kratochvil, A. Kubena On intersection representations of co-planar graphs Discrete Math. 178 No.1-3 251-255 (1998) 1458 H. de Fraysseix, P. Ossona de Mendez, P. Rosenstiehl On triangle contact graphs Combinatorics, Probability and Computing 3 233-246 (1994) 1459 E. Dahlhaus, P. Manuel, M. Miller Maximum h-colourable subgraph problem in balanced graphs Inform. Process. Lett. 65 301-303 (1998) 1460 F. Bonomo, G. Duran, M.D. Safe, A.K. Wagler On minimal forbidden subgraph characterizations of balanced graphs Proceedings of V Latin-American Algorithms, Graphs and Optimization Symposium, Elec. Notes in Discrete Math. 35 41-46 (2009) 1461 A.Z. Salamon, P.G. Jeavons Perfect constraints are tractable Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming CP 2008 Sydney, Australia, Lecture Notes in Computer Science 5202 524-528 (2008) 1462 A.E. Brouwer, A.M. Cohen, A. Neumaier Distance regular graphs Springer Verlag Berlin, New York (1989) 1463 C. Mannino, G. Oriolo, F. Ricci, S. Chandran The stable set problem and the thinness of a graph Operations Research Letters 35 No.1 1-9 (2007) 1464 R.B. Sandeep Perfectly colorable graphs Inform. Process. Lett. 111 No.19 960-961 (2011) doi 10.1016/j.ipl.2011.07.001 1465 N. Nash, D. Gregg An output sensitive algorithm for computing a maximum independent set of a circle graph Inform. Process. Lett. 110 No.16 630-634 (2010) doi 10.1016/j.ipl.2010.05.016 1466 A. Tiskin Fast distance multiplication of unit-Monge matrices Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms SODA 1287-1296 (2010) 1467 R. Uehara Linear time algorithms on chordal bipartite and strongly chordal rgaphs Proceedings 29th Internat. Colloqu. on Automata, Languages and Programming ICALP'02,Lecture Notes in Comp. Sci. 2380 993-1004( 2002) doi 10.1007/3-540-45465-9_85 This article contains an error and was later withdrawn. 1468 P. Heggernes, D. Kratsch Linear-time certifying recognition algorithms and forbidden induced subgraphs Nordic Journal of Computing 14 87-108 (2007) 1469 J.S. Andrade, H.J. Herrmann, R.F.S. Andrade, L.R. da Silva Apollonian Networks: Simultaneously Scale-Free, Small World, Euclidean, Space Filling, and with Matching Graphs Phys. Rev. Lett. 94 018072 (2005) doi 10.1103/PhysRevLett.94.018702 Erratum in Phys. Rev. Lett. 102 079901 (2009) 1470 P.S Kumar, C.S.V. Madhavan A new class of separators and planarity of chordal graphs Lecture Notes in Comp.Sci. 405 30-43 (1989) doi 10.1007/3-540-52048-1_30 1471 L. Markenzon, C.M. Justel, N. Paciornik Subclasses of k-trees: Characterization and recognition Discrete Appl. Math. 154 No.5 818-825 (2006) doi 10.1016/j.dam.2005.05.021 1472 H. Nagamochi, T. Suzuki, T. Ishii A simple recognition algorithm for maximal planar graphs Inform. Proc. Lett. 89 223-226 (2004) doi 10.1016/j.ipl.2002.11.011 1473 M. Conforti, G. Cornuéjols, A. Kapoor, K. Vuskovic Even and odd holes in cap-free graphs J. Graph Theory 30, 289-308 (1999) 1474 C.M.H. de Figueiredo, K. Vuskovic A class of $\beta$-perfect graphs Discrete Math. 216 169-193 (2000) 1475 M. Conforti, G. Cornuéjols, A. Kapoor, K. Vuskovic Triangle-free graphs that are signable without even holes J. Graph Theory 34, 204-220 (2000) 1476 M.V. da Silva, K. Vuskovic Triangulated neighborhoods in even-hole-free graphs Discrete Math. 307 1065-1073 (2007) 1477 I. Parfenoff, F. Roussel, I. Rusu Triangulated neighborhoods in $C_4$-free Berge graphs Proceedings of WG 1999, Lecture Notes in Computer Science 1665, 402-412 (1999) 1478 C.T. Hoang, F. Maffray, M. Mechebbek A characterization of b-perfect graphs Manuscript, 2010 1479 F. Maffray, M. Mechebbek On b-perfect chordal graphs Graphs and Combinatorics 25 365-375 (2009) 1480 M. Badent, C. Binucci, E. Di Giacomo, W. Didimo, S. Felsner, F, Giordano, J. Kratochvil, P. Palladino, M. Patrignani, F. Trotta Homothetic triangle contact representations of planar graphs Proc. of 19th Canadian Conference on Computation Geometry CCCG2007 229-232 (2007) Available here. 1481 M. Kaufmann, J. Kratochvil, K.A. Lehmann, A.R. Subramanian Max-tolerance graphs as intersection graphs: cliques, cycles and recognition Proc. of 17th annual ACM-SIAM symposium on Discrete algorithms SODA'06 832-841 (2006) doi 10.1145/1109557.1109649 1482 M.C. Golumbic, A.N. Trenk Tolerance graphs Cambridge University Press 2004 1483 M.C. Lin, F. Soulignac, J.L. Szwarcfiter The clique operator on circular-arc graphs Discrete Appl. Math. 158 (12) 1259-1267 (2010) 1484 D. Gijswijt, V. Jost, M. Queyranne Clique partitioning of interval graphs with submodular costs on the cliques RAIRO Operations Research 41 275-287 (2007) 1485 A.H. Busch, G. Isaak Recognizing bipartite tolerance graphs in linear time Graph theoretic concepts in computer science. 33rd international workshop, WG '07 Jena, Germany. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 4769 12-20 (2007) 1486 A.H. Busch A characterization of triangle-free tolerance graphs Discrete Appl. Math. 154 No. 3 471-477 (2006) doi 10.1016/j.dam.2005.06.010 1487 D.E. Brown, S.C. Flink, J.R. Lundgren Characterizations of interval bigraphs and unit interval bigraphs Congr. Numerantium 157 79-93 (2002) 1488 D.E. Brown, A.H. Busch, G. Isaak Linear time recognition algorithms and structure theorems for bipartite tolerance graphs and bipartite probe interval graphs DMTCS 12 No.5 63-82 (2010) 1489 G.B. Mertzios, I. Sau, S. Zaks The recognition of tolerance and bounded tolerance graphs Symposium on theoretical aspects of computer science STACS 2010 585-596 (2010) 1490 G.B. Mertzios, D.G. Corneil Vertex splitting and the recognition of trapezoid graphs Discrete Appl. Math. 159 1131-1147 (2011) doi 10.1016/j.dam.2011.03.023 1491 G. Damiand, M. Habib, Ch. Paul A simple paradigm for graph recognition: application to cographs and distance-hereditary graphs Theo. Comp. Sci. 263 99-111 (2001) 1492 H.J. Broersma, C. Hoede Path graphs J. Graph Theory 13 427-444 (1989) 1493 F. Maffray, G. Morel On 3-colorable P5-free graphs Les Cahiers Leibniz No. 191 1494 A. Brandstaedt, V. Giakoumakis Maximum Weight Independent Sets in Hole- and Co-Chair-Free Graphs Inform. Proc. Lett. 112 67-71 (2012) doi 10.1016/j.ipl.2011.09.015 1495 B. Alexeev, A. Fradkin, I. Kim Forbidden induced subgraphs of double-split graphs SIAM J. on Discrete Math. 26 No.1 1-14 (2012) doi 10.1137/100818121 1496 G.B. Mertzios The recognition of triangle graphs Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, 591-602 (2011) doi 10.4230/LIPIcs.STACS.2011.591 1497 G.B. Mertzios An intersection model for multitolerance graphs: Efficient algorithms and hierarchy Proc. of 21 annual ACM-SIAM symposium on Discrete algorithms SODA2011 1306-1317 (2011) 1498 G.B. Mertzios, I. Sau, S. Zaks A new intersection model and improved algorithms for tolerance graphs SIAM J. on Discrete Math. 23(4) 1800-1813 (2009) 1499 W. Wessel, R. Poeschel On circle graphs In: H. Sachs (Ed.) Graphs, Hypergraphs and applications, vol.72 of Teubner-Text Math. 207-210 (1985)