Note: The references are not ordered alphabetically!

1300 A.M. Dean, N.Veytsel
Unit bar-visibility graphs
Congr. Numerantium 160 161-175 (2003)
1301 X. Zhu
Perfect graphs for generalized colouring -- circular perfect graphs
Nesetril, J. (ed.) et al., Graphs, morphisms and statistical physics. Proceedings of the workshop held at Rutgers University, Piscataway, NJ, USA, March 19-21, 2001. Providence, RI: American Mathematical Society (AMS). DIMACS. Series in Discrete Mathematics and Theoretical Computer Science 63, 177-193 (2004)
1302 J. Bang-Jensen, J. Huang
Convex-round graphs are circular-perfect
J. Graph Theory 40, No.3, 182-194 (2002)
1303 X. Zhu
Circular perfect graphs
J. Graph Theory 48 186-209 (2005)
1304 Eschen, Elaine M.; Hoàng, Chính T.; Petrick, Mark D.T.; Sritharan, R
Disjoint clique cutsets in graphs without long holes
J. Graph Theory 48, No.4, 277-298 (2005)
1305 M.U. Gerber, V.V. Lozin
Robust algorithms for the stable set problem
Graphs and Combin., to appear
1306 M.U. Gerber, A. Hertz, V.V. Lozin
Stable sets in two subclasses of banner-free graphs
Discrete Appl. Math. 132 121-136 (2004)
1307 M.U. Gerber, A. Hertz, D. Schindl
P_5-free graphs and the maximum stable set problem
Discrete Appl. Math. 132 109-119 (2004)
1308 Maw-Shang Chang, Ton Kloks, Dieter Kratsch, Kiping Liu, Sheng-Lung Peng
On the recognition of probe graphs of some self-complementary classes of perfect graphs
COCOON 2005, Lecture Notes in Computer Science 3595, 808-817 (2005)
1309 Van Bang Le, H.N. de Ridder
Probe split graphs
Accepted for Discrete Mathematics and Theoretical Computer Science, 2005
1310 Chinh T. Hoang, Van Bang Le
P_4-free colorings and P_4-bipartite graphs
DMTCS 4 109-122 (2001)
1311 Andreas Brandstaedt, Van Bang Le
Structure and linear time recognition of 3-leaf powers
Accepted for Inform. Process. Lett.
1312 D. Rautenbach
Some remarks about leaf roots
Manuscript (2004)
1313 Andreas Brandstaedt, Van Bang Le, R. Sritharan
Structure and linear time recognition of 4-leaf powers
Manuscript (2005)
1314 P.E. Kearney, D.G. Corneil
Tree powers
J. ALgorithms 29 No.1 111-131 (1998)
1315 Nikolopoulos, Stavros D.; Palios, Leonidas
Recognizing HHD-free and Welsh-Powell opposition graphs
Proceedings of WG 2004, Lecture Notes in Computer Science 3353, 105-116 (2004)
1316 A. Berry, M.C. Golumbic, M. Lipshteyn
Cycle-bicolorable graphs and triangulating chordal probe graphs.
1317 S.D. Nikolopoulos, L. Palios
Recognizing HHDS-free graphs
Manuscript, 2005
1318 Put vertical edges in one forest and horizontal edges in the other. (Communicated by P. Ochem)
1319 The edges incident to "old" vertices form a star-forest and the remaining edges (incident to two 2-vertices) form a matching. (Communicated by P. Ochem)
1320 K. Asano
On the genus and thickness of graphs
J. Comb. Theory B 43 287-292 (1987)
ZMath 0627.05022
1321 H. Czemerinski, G. Duran, A. Gravano
Bouchet graphs: A generalization of circle graphs
Congr. Numer. 155 95-108 (2002)
1322 J-H. Yan, J-J. Chen, G.J. Chang
Quasi-threshold graphs
Discrete Appl. Math. 69 No.3 247-255 (1996)
ZMath 0857.05082
1323 Min Chih Lin, Jayme Luiz Szwarcfiter
Efficient construction of unit circular arc models
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, 209-315 (2006)
1324 G. Duran, A. Gravano, R.M. McConnell, J. Spinrad, A. Tucker
Polynomial time recognition of unit circular arc graphs
Journal of Algorithms 58, No.1 67-78 (2006)
1325 Yu, Chang Wu; Chen, Gen Huey
Efficient parallel algorithms for doubly-convex-bipartite graphs
Theoret. Comput. Sci. 147 No.1-2 249-265 (1995)
1326 S.D. Nikolopoulos, L. Palios
Recognizing HH-free, HHD-free and Welsh-Powell opposition graphs
Discrete Mathematics and Theoretical Computer Science Vol.8 65-82 (2006)
1327 Min Chih Lin, Jayme Luiz Szwarcfiter
Characterizations and linear time recognition of Helly circular-arc graphs
Proceedings of the twelfth Annual International Conference on Computing and Combinatorics (COCOON'06), Lecture Notes in Computer Science 4112, 73-82 (2006)
1328 G.A. Duran
Sobre grafos intersección de arcos y cuerdas en un círculo
Doctoral dissertation, Universidad de Buenos Aires, 2000. (In Spanish.)
Available here. See also the note at
J. Bang--Jensen, P. Hell
On chordal proper circular arc graphs
Discrete Math. 128 1994 395--398
1329 J.A. Gallian
A dynamic survey of graph labelling
Elec. J. Combin. DS6
Available here
1330 A. Rosa
On Certain Valuations of the Vertices of a Graph
Theory of graph (international symposium, Rome, July 1966) Gordon and Breach N.Y. and Dunod Paris 349-355 (1967)
1331 S.W. Golomb
How to number a graph
In: Graph Theory and Computing, Ed. R.C. Read. Academic Press (1972) 23-37
1332 R.L. Graham, N. Sloane
On additive bases and harmonious graphs
SIAM J. Algebraic Discrete Math. 1 382-404 (1980)
1333 A.A. Krishnaa, M.S. Dulawat, G.S. Rathore
Computational complexity in decision problems
Conf. of Raj. Parishad, Dec. 14-15 (2001), Udaipur, India
1334 R. Shamir, D. Tsur
Faster subtree isomorphism
Congr. Numer. 140 33-42 (1999)
1335 D.B. Chandler, M-S Chang, T. Kloks, J. Liu, S-L Peng
Recognition of probe cographs and partitioned probe distance hereditary graphs
Proceedings of AAIM 2006, LNCS 4041 267-278 (2006)
1336 D.B. Chandler, M-S Chang, T. Kloks, J. Liu, S-L Peng
Partitioned probe comparability graphs
Proceedings of WG 2006, LNCS 4271 179-190 (2006)
1337 D.B. Chandler, M-S Chang, A.J.J. Kloks, J. Liu, S-L Peng
On probe permutation graphs
Proceedings of TAMC 2006, LNCS 3959 494-504 (2006)
1338 A. Bretscher, D.G. Corneil, M. Habib, C. Paul
A simple linear time LexBFS cograph recognition algorithm
Proceedings of WG2003, LNCS 2880 119-130 (2003)
1339 D.E. Brown, J.R. Lundgren, C. Miller
Variations on interval graphs
Congr. Numerantium 149 77-95 (2001)
1340 T. Kloks, C.-S. Liu, S.-L. Peng
Domination and independent domination on probe interval graphs
Proceedings of 23rd Workshop on Combinatorial Mathematics and Computation Theory 93-97 (2006)
Available here
1341 Min Chih Lin, Jayme L. Szwarcfiter
Faster recognition of clique-Helly and hereditary clique-Helly graphs
Information Processing Letters 103 40-43 (2007)
1342 H.S. Chao, F.R. Hsu, R.C.T. Lee
An Optimal Algorithm for Finding the Minimum Cardinality Dominating Set on Permutation Graphs
Discrete Appl. Math. 102, No.3 159-173 (2000)
ZMath 1052.90095
1343 Van Bang Le, H.N. de Ridder
Characterisations and linear-time recognition of probe cographs
Accepted for WG 2007
1344 Daniel Bayer
Ueber probe trivially-perfect und probe-Cographen
Diplomarbeit, Universitaet Rostock 2006
1345 H.N. de Ridder
On probe classes of graphs
Ph.D. Thesis, Rostock 2007
1346 N.V.R. Mahadev, B.A. Reed
A note on vertex orders for stability number
J. Graph Theory 30 113-120 (1999)
1347 J. Enright, L. Stewart
Subtree filament graphs are subtree overlap graphs
Information Proc. Letters Vol. 104 Nr.6 228-232 (2007)
1348 Subtree overlap graphs are string graphs by the following construction: for each subtree, draw a string around the subtree such that if subtree A is contained in subtree B, then string A is closer to the tree model than string B (then string A and string B do not intersect). If subtree A and subtree B are disjoint then their corresponding string do not intersect. If subtree A and subtree B overlap then their corresponding string intersect. (P. Ochem)
1349 V.L. Lozin, M. Milanic
On finding augmenting graphs
Rutcor Research Report 28-2005 appear in Discrete Appl. Math.
1350 V.E. Alekseev
On easy and hard hereditary classes of graphs with respect to the independent set problem
Discrete Appl. Math. 132, No.1-3 17-26 (2003)
1351 V.E. Alekseev, V.V. Lozin
Augmenting graphs for independent sets
Discrete Appl. Math. 145, No.1 3-10 (2004)
1352 R. Mosca
Independent sets in certain P_6-free graphs
Discrete Applied Math. 92 177-191 (1999)
1353 A. Brandstaedt, C.T. Hoang
On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
Theoretical Comp. Sci. 389, No.1-2, 295-306 (2007)
1354 D.B. Chandler, M-S Chang, A.J.J. Kloks, J.P. Liu, S-L Peng
On probe permutation graphs
Proceedings of Cocoon 2008, LNCS 5092, 468-477 (2008)
1355 D.B. Chandler, M-S Chang, T. Kloks, V.B. Le, S-L Peng
Probe ptolemaic graphs
Discrete Appl. Math. 157 No.12, 2611-2619 (2009)
1356 A. Brandstaedt, V.B. Le, D. Rautenbach
A forbidden subgraph characterization of distance-hereditary 5-leaf powers
Discrete Math. 309 3843-3852 (2009)
1357 M.C. Golumbic, F. Maffray, G. Morel
A characterization of chain probe graphs
Annals of Operations Research (2009)
1358 T. Kloks, H. Mueller, K. Vuskovic
Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
J. Comb. Theory B 99 733-800 (2009)
1359 D.B. Chandler, J. Guo, T. Kloks, R. Niedermeier
Probe matrix problem: Totally balanced matrices
Proceedings of AAIM 2007, LNCS 4508 368-377 (2007)
1360 Y. Wu, W. Zang, C-Q Zhang
A characterization of almost CIS graphs
Rutcor Research Report RRR 01-2009
1361 D. V. Andrade, E. Boros, V. Gurvich
On graphs whose maximal cliques and stable sets intersect
Rutcor Research Report RRR 17-2006
1362 F. Gurski, E. Wanke
On module-composed graphs
35th Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. WG'09,Lecture Notes in Comp. Sci. 5911 166--177 (2009)
1363 Forbidden classes generated from the definition by computer search (H.N. de Ridder; an error corrected by M.D. Safe).
1364 R.B. Hayward
Bull-free weakly chordal perfectly orderable graphs
Graphs and Combin. 17:479-500 (2001)
1365 J-L Fouquet, F. Roussel, P. Rubio, H. Thuillier
New classes of perfectly orderable graphs
Discrete Math. 236 No.1-3 95-109 (2001)
ZMath 0998.05056
1366 V.G.P. de Sa, G.D. da Fonseca, R. Machado, C.M.H. de Figueiredo
Complexity dichotomy on partial grid recognition
International Symposim on Combinatorial Optimization 2010, to appear in Elec. Notes in Discrete Math.
1367 S.N. Bhatt S.S. Cosmadakis
The complexity of minimizing wire lengths in VLSI layouts
Inform. Process Lett. 25 253-267 (1987)
1368 A. Gregori
Unit-length embedding of binary trees on a square grid
Inform. Process Lett. 31 167-173 (1989)
1369 F. Bonomo, G. Duran, L.N. Grippo, M.D. Safe
Partial characterizations of circular-arc graphs
Journal of Graph Th. Vol.61 Nr.4 289-306 (2009)
1370 J. Kratochvil, J Nesetril
Independent set and clique problems in intersection defined graphs
Commentationes Mathematicae Universitatis Carolinae Vol. 31 No.1 85-93 (1990)
1371 Consider the "unsubdivided" planar graph and put its vertices horizontally according to a weak bar visibility representation, then put vertically the pairs of subdivision vertices. (P. Ochem, personal communication)
1372 Straightforward (P. Ochem, personal communication)
1373 J. Chalopin, D. Goncalves
Every planar graph is the intersection graph of segments in the plane
ACM Symposium on the Theory of Computing STOC'09 (2009)
1374 N. de Castro, F.J. Cobos, J.C. Dana, A. Marquez
Triangle-free planar graphs as segment intersection graphs
Journal of Graph Algorithms and Applications Vol.6 No.1 7-26 (2002)
1375 H. Groetzsch
Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz fuer dreikreisfreie Netze auf der Kugel
Wiss. Z. Martin-Luther-U. Halle-Wittenberg, Math.-Nat Reihe 8 109-120 (1959)
1376 J. Chalopin, D. Goncalves, P. Ochem
Planar graphs are in 1-STRING
Proc. of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms SODA 609-617 (2007)
1377 A graph G is a line graph iff it is the EPT graph of a star.
1378 From the forbidden subgraph characterization of line graphs, see also
A. Brandstaedt, V.B. Le, J. Spinrad
Graph classes: a survey
SIAM Monographs on discrete mathematics and applications (1999)
F. Harary, C. Holtzmann
Line graphs of bipartite graphs
Rev. Soc. Mat. Chile 1 19-22 (1974)
1379 F. Gurski, E. Wanke
The clique-width of tree-power and leaf-power graphs
Proceedings of WG 2007, Lecture Notes in Computer Science 4769, 76-85 (2007)
1380 N. Garg, V.V. Vazirani H. Yannakakis
Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
Proceedings 20th Internat. Colloqu. on Automata, Languages and Programming ICALP'93,Lecture Notes in Comp. Sci. 700 64-75 (1993)
1381 Let T = (V, E) be a tree, and P a collection of subpaths of the tree. An "integral flow on T" (with unit capacities) is a subset P' of P such that the paths in P' are edge-disjoint. (In the undirected multicommodity flow-in-a-tree setting, we think of there being one commodity for each path --- the source/sink for this commodity are located at the endpoints of the path. Moreover in multicommodity flow we think more directly of routing a particular integral amount of each flow, but with unit edge capacities, we either can route 0 or 1 unit of each commodity, and the commodities for which we chose to route 1 unit of flow must be edge-disjoint, or else we'll violate an edge capacity.) This integral flow is the same as an independent set in the intersection graph (P, F) where {p1, p2} is in F iff p1 and p2 share an edge. An EPT graph is exactly an intersection graph of this type.
So given an EPT graph (P, F) along with its tree-representation (T=(V,E), P), we can find a max-weight independent set in polytime via Theorem 5 of
N. Garg, V.V. Vazirani H. Yannakakis
Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
Proceedings 20th Internat. Colloqu. on Automata, Languages and Programming ICALP'93,Lecture Notes in Comp. Sci. 700 64-75 (1993)
. (D. Pritchard)
1382 A. Brandstaedt, V.B. Le, J. Spinrad
Graph classes: a survey
SIAM Monographs on discrete mathematics and applications (1999)
1383 Every maximal independent set is a minimal dominating set.
1384 Since every tree is a 2-interval graph
W.T. Trotter, Jr., F. Harary
On double and multiple interval graphs
J. Graph Theory 3 1979 205--211
J.R. Griggs, D.B. West
Extremal values of the interval number of a graph
SIAM J. Alg. Discr. Meth. 1 1979 1--7
and block graphs are created from trees by replacing edges by cliques, block graphs are 2-interval graphs as well.
1385 B. Courcelle, s. Olariu
Upper bounds to the clique width of graphs
Discrete Appl. Math. 101 77-114 (2000)
1386 H.-O. Le
Contributions to clique-width of graphs
Ph.D.-Thesis Rostock (2003)
1387 M.C. Dourado, F. Protti, J.L. Szwarcfiter
Complexity aspects of the Helly property: Graphs and hypergraphs
The Elec. J. of Combin. Dynamic Survey #DS17 (2009)
1388 To construct a circle model for a distance-hereditary graph, add a chord near the endpoint of an existing chord, crossing it, for adding a pendant vertex; replace a chord by two parallel chords for adding false twin; and replace chord by two crossing chords for adding true twins.
1389 L.S. Chandran, M.C. Francis, S. Suresh
Boxicity of Halin graphs
Discrete Math. 309 3233-3237 (2009)
1390 A. Gyarfas, D. Kratsch, J. Lehel, F. Maffray
Minimal non-neighborhood-perfect graphs
J. Graph Theory 21 issue 1 55-66 (1996)
1391 Halin graphs, outerplanar graphs are a proper subclass of Boxicity 2 graphs as Halin graphs, outerplanar graphs are all planar but Boxicity 2 graphs include large complete graphs. (Mathew C. Francis)
1392 Because the 2-subdivision of a graph replaces every edge by a P4 .
1393 Because the comparability graph of a height 2 poset is a bipartite graph.
1394 F. Gurski
Graph operations on clique-width bounded graphs
Arxiv preprint cs/0701185 (2007)
On arxiv
1395 D. Kratsch, J.P. Spinrad, R. Sritharan
A new characterization of HH-free graphs
Discrete Math. 308 4833-4835 (2008)
1396 J.P. Hutchinsion, T. Shermer, A. Vince
On representations of some thickness-two graphs
Proceedings of Graph Drawing '95, LNCS 1027, 324-332 (1996)
1397 Assign every maximal clique C a point pC on the real line and every vertex v a set of intervals on the real line, one interval for every maximal clique B containing v, such that the interval contains precisely pB.
1398 Every maximal outerplanar graph is a triangulation of a polygon.
1399 M. Crochemore, D. Hermelin, G. M. Landau, D. Rawitz, S. Vialette
Approximating the 2-Interval Pattern Problem
Theoretical Comp. Sci. 395 No. 2-3, 283-297 (2008)