Note: The references are not ordered alphabetically!

1500 K3,3 is a discriminating graph.
1501 G. Duran, M.C. Lin
Clique graphs of Helly circular-arc graphs
Ars Combin. 60 255-271 (2001)
1502 G. Duran, M.C. Lin
On some subclasses of circular-arc graphs
Technical Report TR003-99 Departamento de Computacion, FCEyN, Universided de Buenos Aires (1999)
1503 B. Hedman
Clique graphs of time graphs
J. Combin. Theory Ser. B. 37 (3) 270-278 (1968)
1504 For any graph G, if we add a universal vertex vertex v, G+v is a dually chordal graph. This fact allows a trivial reduction, since the new vertex increases the chromatic number and the size of the largest clique by exactly 1. (Communicated by Vinicius Santos)
Furthermore, the clique cover number of G and G+v are equal, hence we have a reduction for clique cover, as well. (Communicated by Arne Leitert)
1505 A. Leitert
3-Colourability of dually chordal graphs in linear time
Manuscript, 2012
Available on arxiv.
1506 For any connected graph G, if we add a universal vertex vertex v, H = G+v is a locally connected graph. This fact allows a trivial reduction, since the new vertex increases the chromatic number and the size of the largest clique by exactly 1. Furthermore, the clique cover number of G and G+v are equal, hence we have a reduction for clique cover, as well. Similarly for independent set. (Communicated by Pavel Irzhavski). Treewidth is reduced analogously to clique (Communicated by Arne Leitert). For the domination problem, we add a true twin to every vertex (V*={v, v* | v in V} and E*={uv, u*v, uv*, u*v* | uv in E}). Then every dominating set in G is also dominating in G* and a minimal dominating set in G* can be converted to a minimal dominating set in G by replacing every vertex v* in the set by v (Communicated by Arne Leitert).
1507 P. Heggernes, P. van 't Hof, D. Lokshtanov, J. Nederlof
Computing the cutwidth of bipartite permutation graphs in linear time
Proceedings of the 36th international conference on Graph-theoretic concepts in computer science WG 2010 75-87 (2010)
Available here.
1508 D.M. Thilikos, M. Serna, H.L. Bodlaender
Cutwidth I: a linear time fixed parameter algorithm
J. of Algorithms 56 Issue 1 1-24 (2005)
1509 B. Monien, I.H. Sudborough
Min cut is NP-complete for edge weighted trees
Theoretical Comp. Sci. 58 Issue 1-3, 209-229 (1988)
1510 P. Heggernes, D. Lokshtanov, R. Mihai, C. Papadopoulos
Cutwidth of split graphs, threshold graphs, and proper interval graphs
Proceedings of WG 2008, LNCS 5344, pp. 218-229 (2008)
1511 J. Diaz, M. Penrose, J. Petit, M. Serna
Approximating layout problems on random geometric graphs
Journal of Algorithms 39 78-117 (2001)
1512 J. Diaz, J. Petit, M. Serna
A survey on graph layout problems
ACM Computing surveys 34 313-356 (2002)
1513 J. Yuan, S. Zhou
Optimal labelling of unit interval graphs
Appl. Math. J. Chinese Univ. Ser. B (English edition) 10 337-344 (1995)
1514 M. Yannakakis
A polynomial algorithm for the min cut linear arrangement of trees
Journal of ACM Vol 32, 950-988 (1985)
1515 D.M. Thilikos, M. Serna, H.L. Bodlaender
Cutwidth II: algorithms for partial w-trees of bounded degree
J. of Algorithms 56 Issue 1 25-49 (2005)
1516 H. ElGindy
Hierarchical decomposition of polygons with applications
Ph.D. Thesis, McGill University (1985)
1517 H. Mueller
Hamiltonian circuits in chordal bipartite graphs
Discrete Math. 156 291-298 (1996)
doi 10.1016/0012-365X(95)00057-4
1518 P. Damaschke
The Hamiltonian circuit problem for circle graphs is NP-complete
Information Proc. Lett. 32 No.1 1-2 (1989)
doi 10.1016/0020-0190(89)90059-8
1519 G. Narasimhan
A note on the Hamiltonian Circuit Problem on directed path graphs
Information Proc. Lett. 32 No.4 167-170 (1989)
doi 10.1016/0020-0190(89)90038-0
1520 A.A. Bertossi, M.A. Bonuccelli
Hamiltonian Circuits in interval graph generalizations
Information Proc. Lett. 23 195-200 (1986)
1521 A.A. Bertossi
The edge Hamiltonian path problem is NP-complete
Information Proc. Lett. 13 157-159 (1981)
1522 T.-H. Lai, S.-S. Wei
The edge Hamiltonian path problem is NP-complete for bipartite graphs
Information Proc. Lett. 46 No.1 21-26 (1993)
1523 T. Akiyama, T. Nishizeki, N. Saito
NP-completeness of the Hamiltonian cycle problem for bipartite graphs
J. Inf. Process. V.3 73-76 (1980)
1524 J.S. Deogun, G. Steiner
Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
SIAM J. Computing 23 Issue 3 520-552 (1994)
doi 10.1137/S0097539791200375
1525 C.J. Colbourn, L.K. Stewart
Dominating cycles in series-parallel graphs
Ars Combin. 19A 107-112 (1985)
1526 B.S. Panda, D. Pradhan
NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs
Manuscript
Available on arXiv.
1527 W.K. Shih, T.C. Chen, W.L. Hsu
An O(n^2 log n) algorithm for the Hamiltonian cycle problem on circular-arc graphs
SIAM J. Comput. 21 No.6 1026-1046 (1992)
1528 L. Ibarra
A simple algorithm to find Hamiltonian cycles in proper interval graphs
Information Proc. Lett. 109 Issue 18 1105-1108 (2009)
1529 J.M. Keil
Finding hamiltonian circuits in interval graphs
Information Proc. Lett. 20 201-206 (1985)
1530 B.S. Panda, S.K. Das
A linear time recognition algorithm for proper interval graphs
Information Proc. Lett. 87 153-161 (2003)
1531 A.A. Bertossi
Finding hamiltonian circuits in proper interval graphs
Information Proc. Lett. 17 97-101 (1983)
1532 G.K. Manacher, T.A. Mankus, C.J. Smith
An optimum θ(n log n) algorithm for finding a canonical hamiltonian path and a canonical hamiltonian circuit in a set of intervals
Information Proc. Lett. 35 205-211 (1990)
1533 M.S. Krisnamoorthy
An NP-hard problem in bipartite graphs
SIGACT News 7 26-26 (1976)
1534 R.W. Hung, M.S. Chang
Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
Theoret. Comput. Sci. 341 411-440 (2005)
1535 S.Y. Hsieh, C.W. Ho, T.S. Hsu, M.T. Ko
The Hamiltonian problem on distance-hereditary graphs
Discrete Appl. Math. 153 508-524 (2006)
1536 R.-W. Hung, M.-S. Chang, C.-H. Laio
The Hamiltonian cycle problem on circular-arc graphs
Proc. of the International MultiConference of Engineers and Computer Scientists IMECS 2009
1537 A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter
Hamiltonian paths in grid graphs
SIAM J. Comput. Vol.11 No.4 676-686 (1982)
1538 C. Umans, W. Lenhart
Hamiltonian cycles in solid grid graphs
Proc. of Foundations in Comp. Sci. FOCS 1997 496-505 (1997)
1539 M.R. Garey, D.S. Johnson, R.E. Tarjan
The planar Hamiltonian circuit problem is NP-complete
SIAM J. Comput. Vol.5 704-714 (1976)
1540 V.I. Benediktovich, V.I. Sarvanov
Hamiltonian cycle problem for planar cubic graphs
Doklady of the academy of sciences of Belarus No.1 34-37 (1997)
1541 Hamiltonian cycle is NP-complete for locally connected graphs. Add a universal vertex u to a graph G. G has a Hamiltonian path if and only if G+u has a Hamiltonian cycle.
=>: G has a Hamiltonian path with starting vertex s and ending vertex e. Thus, (s, ..., e, u, s) is a Hamiltonian cycle in G+u.
<=: G+u has a Hamiltonian cycle. Therefore u has two neighbours s and e in the cycle. Thus (s, ..., e) is a Hamiltonian path in G. (Communicated by Arne Leitert, Pavel Irzhavski)
1542 H. Sachs
Über selbstkomplementäre Graphen
Publ. Math. Debrecen 9 270-288 (1962)
1543 G.B. Mertzios, I. Bezakova
Computing and counting longest paths on circular-arc graphs in polynomial time
Discrete Appl. Math, in press
doi 10.1016/j.dam.2012.08.024
1544 It is well known that the tree-width of a chordal graph is one less than its maximal clique. It is also well known that a planer graph can not have any clique of size 5 or greater, hence chordal \cap planar has treewidth at most 3 (Communicated by Vatshelle)
1545 A. Asinowski, E. Cohen, M.C. Golumbic, V. Limouzy, M. Lipshteyn, M. Stern
Vertex intersection graphs of paths on a grid
Journal of Graph Algorithms and Applications Vol.16 No.2 129-150 (2012)
1546 M. Middendorf, F. Pfeiffer
The max clique problem in classes of string-graphs
Discrete Math. 108 365-372 (1992)
1547 K. Appel, W. Haken
Every planar map is four colorable Part I. Discharging
Illinois J. of Math. 21 429-490 (1977)
1548 K. Appel, W. Haken
Every planar map is four colorable Part II. Reducibility
Illinois J. of Math. 21 491-567 (1977)
1549 K. Appel, W. Haken
Every planar map is four-colorable
American Mathematical Society (1989)
1550 F. Gurski
Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
Discrete Math. 306 No.2 271-277 (2006)
doi 10.1016/j.disc.2005.11.014
1551 D. Eppstein described this class in an answer to a question of Y. Cao.
1552 A. Butman, D. Hermelin, M. Lewenstein, D. Rawitz
Optimization problems in multiple-interval graphs
Proc. of 17th annual ACM-SIAM symposium on Discrete algorithms SODA2007 268-277 (2007)
1553 M.C. Francis, D. Goncalves, P. Ochem
The maximum clique problem in multiple interval graphs
Proceedings of WG 2012, Lecture Notes in Computer Science 7551, 57-68 (2012)
1554 F. Koenig
Sorting with objectives
Ph.D. thesis, Technische Universitaet Berlin (2009)
1555 V.S. Gordon, Y.L. Orlovich, C.N. Potts, V.A. Strusevich
Hamiltonian properties of locally connected graphs with bounded vertex degree
Discrete Appl. Math. 159 1759-1774 (2011)
1556 G. Chartrand, R. Pippert
Locally connected graphs
Casopis Pest. M at. 99 158-163 (1974)
1557 A. Abueida, R. Sritharan
Cycle extendability and hamiltonian cycles in chordal graph classes
SIAM J. Discrete Math. 20 669-681 (2006)
1558 T. Jiang
Planar Hamiltonian chordal graphs are cycle extendable
Discrete Math. 257 441-444 (2002)
1559 G.R.T. Hendry
Extending cycles in graphs
Discrete Math. 85 59-72 (1990)
1560 C. Picouleau
Complexity of the Hamiltonian cycle in regular graph problem
Theoret. Comput. Sci. 131 463-473 (1994)
doi 10.1016/0304-3975(94)90185-6
1561 D. Tankus, M. Tarsi
The structure of well-covered graphs and the complexity of their recognition problems
J. Combin. Th. Series B 69 No.2 230-233 (1997)
doi 10.1006/jctb.1996.1742
1562 D. Tankus, M. Tarsi
Well-covered claw-free graphs
J. Combin. Th. Series B 66 No.2 293-302 (1996)
doi 10.1006/jctb.1996.0022
1563 M. Lesk, M.D. Plummer, W.R. Pulleyblank
Equi-matchable graphs
Graph theory and combinatorics (Cambridge, 1983), 239–254, Academic Press, London, 1984
1564 M.D. Plummer
Well-covered graphs: A survey
Quaestiones Math. 16 No.3 253-287
1565 E.M. Arkin, S.P. Fekete, K. Islam, H. Meijer, J.S.B. Mitchell, Y. Nunez-Rodriguez, V. Polishchuk, D. Rappaport, H. Xiao
A study of grid hamiltonicity: Not being (super)thin or solid is hard
Computational Geometry: Theory and Applications 42 No.6-7 582-605 (2009)
1566 V.S. Gordon, Y.L. Orlovich, F. Werner
Hamiltonian properties of triangular grid graphs
Discrete Math. 308 6166-6188 (2008)
1567 D.J. Oberly, S.K. Simic, D.P. Sumner
Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
J. Graph Th. Vol.3 No.4 351-356 (1979)
1568 J.R. Reay, T. Zamfirescu
Hamiltonian cycles in T-graphs
Discrete Comput. Geom. 24 497-502 (2000)
1569 Yu.L. Orlovich
On locally connected graphs whose maximal vertex degree is at most four
Vestsi Nats. Akad. Navuk Belarusi. Ser. Fiz.-Mat. Navuk No.3 97-100 (1999)
1570 Z. Ryjacek
Almost claw-free graphs
J. Graph Theory 18 No.5 469-477 (1994)
doi 10.1002/jgt.3190180505
1571 M. de Berg, O. Cheong, M. van Kreveld, M. Overmars
Computation geometry: Algorithms and applications
Springer Verlag (2008)
1572 T. Hiroshima, Y. Miyamoto, K. Sugihara
Computation geometry: Algorithms and applications
IEICE Trans. Fundamentals Vol. E83 A, No.4 627-638 (2000)
1573 D.E. Taylor, R. Levingston
Distance-regular graphs
Proceedings of the International Conference on Combinatorial Theory, Lecture Notes in Mathematics 686, 313–323 (1978)
1574 P. Festa, P.M. Pardalos, M.G.C. Resende
Feedback set problems
in: D.Z. Du, P.M. Pardalos, Handbook of Combinatorial Optimization, Supplement vol. A, Kluwer Academic Publishers, 209-259 (2000)
1575 A. Brandstaedt
On improved time bounds for permutation graph problems
Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. 1993, Lecture Notes in Comp. Sci. 657 1-10 (1993)
1576 Y.D. Liang
On the feedback vertex set problem in permutation graphs
Information Proc. Lett. 52 123-129 (1994)
doi 10.1016/0020-0190(94)00133-2
1577 C.L. Lu, C.Y. Tang
A linear-time algorithm for the weighted feedback vertex problem on interval graphs
Information Proc. Lett. 61 107-111 (1997)
1578 S.R. Coorg, C.P. Rangan
Feedback vertex set on cocomparability graphs
Networks 26 101-111 (1995)
1579 M.S Chang, Y.D. Liang
Minimum feedback vertex set in cocomparability graphs and convex bipartite graphs
Acta Informatica 34 337-346 (1997)
1580 C. Wang, T. Liu, W. Jian, K. Xu
Feedback vertex set on tree convex bipartite graphs
Proceedings of COCOA 2012 LNCS 7402 95-102 (2012)
1581 Feedback vertex set on AT-free graphs
D. Kratsch, H. Mueller, I. Todinca
Discrete Appl. Math. 156 No. 10 1936-1947 (2008)
doi 10.1016/j.dam.2007.10.006
1582 B. Courcelle, S. Oum
Vertex-minors, monadic second-order logic and a conjecture by Seese
J. Comb. Theory (B) 97 91-126 (2007)
1582 B. Courcelle, S. Oum
Vertex-minors, monadic second-order logic and a conjecture by Seese
J. Comb. Theory (B) 97 91-126 (2007)
1583 T. Kloks, C.-H. Liu, S.-H. Poon
Feedback vertex set on chordal bipartite graphs
Manuscript (2012)
Available on arXiv.
1584 A. Takaoka, S. Tayu, S. Ueno
On minimum feedback vertex set in graphs
Third Internation Conference on Networking and Computing 429-434 (2012)
doi 10.1109/ICNC.2012.81
1585 F. Gavril
Minimum weight feedback vertex sets in circle graphs
Information Proc. Lett. 107 No.1 1-6 (2008)
doi 10.1016/j.ipl.2007.12.003
1586 S. Ueno, Y. Kajitani, S. Gotoh
On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
Discrete Math. 72 No.1-3 355-360 (1988)
doi 10.1016/0012-365X(88)90226-9
1587 D. Li, Y. Liu,
A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph
Acta Math. Sci. (English Ed.) 19 (1999), no. 4, 375–381
1588 The decycling number of graphs
S. Bau, L.W. Beineke
Australas. J. Comb. 25 285-298 (2002)
1589 R.M. Karp
Reducibility among combinatorial problems
Complexity of Computer Computations (R.E. Miller, J.W. Thatcher, ed.), Plenum Press, New York-London 85-103 (1972)
1590 W. Jiang, T. Liu, T. Ren, K. Xu
Two hardness results on feedback vertex sets
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management; Lecture Notes in Computer Science 6681 233-243 (2011)
1591 W. Jiang, T. Liu, K. Xu
Tractable feedback vertex sets in restricted bipartite graphs
Proceedings of COCOA 2011 Lecture Notes in Computer Science 6831, 424-434 (2011)
1592 E. Speckenmeyer
On feedback vertex sets and nonseparating independent sets in cubic graphs
J. of Graph Theory 12 No.3 405-412 (1988)
doi 10.1002/jgt.3190120311
1593 Feedback vertex set is NP-complete for planar graph of maximum degree 4. By subdividing each edge by one new vertex, it easily follows that feedback vertex set is also NP-complete on bipartite planar graphs of maximum degree 4 (V.B. Le).
1594 J.M. Keil, L. Stewart
Approximating the minimum cover and other hard problems in subtree filament graphs
Discrete Appl. Math. 154 1983-1995 (2006)
1595 F. Gavril
Minimum weight feedback vertex sets in circle n-gon graphs and circle trapezoid graph
Discrete Math. Algorithm. Appl. 3, 323-336 (2011)
doi 10.1142/S1793830911001243
1596 Y.-L. Lin
Circular and circle trapezoid graphs
J. Sci. Eng. Tech. 2 11-17 (2006)
1597 D. Kratsch, T. Kloks, H. Mueller
Measuring the vulnerability for classes of intersection graphs
Discrete Appl. Math. 77 259-270 (1997)
1598 M.M. Halldorson, S. Kitaev, A. Pyatkin
Alternation graphs
Proceedings of WG 2011, Lecture Notes in Computer Science 6986, 191-202 (2011)
1599 S. Kitaev, A. Pyatkin
On representable graphs
Automata, languages and Combinatorics 13 No.1 45-54 (2008)