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]
, Th.7.
M.C. Lin, F. Soulignac, J.L. Szwarcfiter
The clique operator on circular-arc graphs Discrete Appl. Math. 158 (12) 1259-1267 (2010) |
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) |