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) ZMath 1060.05035 |
1302 |
J. Bang-Jensen, J. Huang Convex-round graphs are circular-perfect J. Graph Theory 40, No.3, 182-194 (2002) ZMath 1006.05054 |
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) ZMath 1061.05067 |
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) ZMath 0919.68055 |
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. Submitted |
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
[68]
.
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 http://rutcor.rutgers.edu/pub/rrr/reports2005/38_2005.pdfTo 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 http://rutcor.rutgers.edu/pub/rrr/reports2009/01_2009.pdf |
1361 |
D. V. Andrade, E. Boros, V. Gurvich On graphs whose maximal cliques and stable sets intersect Rutcor Research Report RRR 17-2006 http://rutcor.rutgers.edu/pub/rrr/reports2006/17_2006.pdf |
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) JGAA |
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
[1382]
,
A. Brandstaedt, V.B. Le, J. Spinrad
Graph classes: a survey SIAM Monographs on discrete mathematics and applications (1999)
[1623]
.
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
[1380]
. (D. Pritchard)
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) |
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
[1031]
W.T. Trotter, Jr., F. Harary
On double and multiple interval graphs J. Graph Theory 3 1979 205--211
[472]
and block graphs are created from trees by replacing
edges by cliques, block graphs are 2-interval graphs as well.
J.R. Griggs, D.B. West
Extremal values of the interval number of a graph SIAM J. Alg. Discr. Meth. 1 1979 1--7 |
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) EJCS |
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 are a proper subclass of Boxicity 2 graphs as Halin graphs are all planar but Boxicity 2 graphs include large complete graphs. Outerplanar graphs are a proper subclass of Boxicity 2 graphs as 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) |