Note: The references are not ordered alphabetically!

 1600 D. Eppstein Recognizing partial cubes in quadratic time Journal of Graph Algorithms and Applications Vol.15 No.2 269-293 (2011) JGAA 1601 S. Ovchinnikov Graphs and cubes Universitext, Springer 2011 1602 W. Imrich, S. Klavzar A simple O(mn) algorithm for recognizing Hamming graphs Bull. Inst. Combin. Appl. 9 45-56 (1993) 1603 P. Winkler Isometric embeddings in products of complete graphs Discrete Appl. Math. 7 221-225 (1984) 1604 W. Imrich, S. Klavzar Recognizing Hamming graphs in linear time and space Information Proc. Lett. 63 No.2 91-95 (1997) 1605 H.-J. Bandelt, V. Chepoi Metric graph theory and geometry: a survey Contemporary Mathematics 453 49-86 (2008) 1606 W. Imrich, S. Klavzar, H.M. Mulder Median graphs and triangle-free graphs SIAM J. Discrete Math. 12 111-118 (1999) doi 10.1137/S0895480197323494 1607 W. Imrich, S. Klavzar A Convexity Lemma and Expansion Procedures for Bipartite Graphs European J. Combin. 19 No.6 677-685 (1998) Note that there is an error in this article, see [1608] B. Bresar, W. Imrich, S. Klavzar Fast recognition algorithms for classes of partial cubes Discrete Appl. Math. 131 No.1 51-61 (2003) . 1608 B. Bresar, W. Imrich, S. Klavzar Fast recognition algorithms for classes of partial cubes Discrete Appl. Math. 131 No.1 51-61 (2003) doi 10.1016/S0166-218X(02)00416-X 1609 Y. Otachi, Y. Okamoto, K. Yamazaki Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs Discrete Appl. Math. 155 No.17 2383-2390 (2007) doi 10.1016/j.dam.2007.07.010 1610 A. Brandstaedt, F.F. Dragan, E. Koehler Linear time algorithms for the Hamiltonian problems on (claw,net)-free graphs SIAM J. Computing 30 1662-1677 (2000) 1611 D. Krumme, K. Venkataraman, G. Cybenko Hypercube embedding is NP-complete In Heath, M., editor, Hypercube Microprocessors SIAM, Philadelphia (1986) 1612 F. Harary Cubical graphs and cubical dimensions Computers & Mathematics with Applications No.15 271–275 (1988) 1613 F. Harary, J.P. Hayes, H.-J. Wu A survey of the theory of hypercube graphs Computers & Mathematics with Applications No.15 277–289 (1988) 1614 F. Afrati, C.H. Papadimitriou, G. Papageorgiou The complexity of cubical graphs Information and control 66 53-60 (1985) 1615 I. Havel, J. Moravek B-valuations of graphs Czech. Math. J. 22 338-352 (1972) 1616 D. Goncalves, A. Pinlou, M. Rao, S. Thomasse The domination number of grids SIAM J. Discrete Math. 25 No.3 1443-1453 (2011) 1617 W.T. Trotter Jr. A Characterization of Roberts' Inequality for Boxicity Discrete Math. 28 303-313 (1979) 1618 T.M. Chan A note on maximum independent sets in rectangle intersection graphs Inform. Proc. Lett. 89 19-23 (2004) 1619 L. Alcón, L. Faria, C.M.H. de Figueiredo, M. Gutierrez The complexity of clique graph recognition Theoret. Comput. Sci. 410 2072-2083 (2009) doi 10.1016/j.tcs.2009.01.018 1620 K-i. Kawarabayashi Planarity allowing few error vertices in linear time Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS '09) 639-648 (2009) doi 10.1109/FOCS.2009.45 1621 B. Mohar Face covers and the genus problem for apex graphs J. Combin. Theory (B), 82(1) 102-117 (2000) doi 10.1006/jctb.2000.2026 1622 D. Bienstock, C.L. Monma On the complexity of embedding planar graphs to minimize certain distance measures Algorithmica 5 92-109 (1990) 1623 F. Harary, C. Holtzmann Line graphs of bipartite graphs Rev. Soc. Mat. Chile 1 19-22 (1974) 1624 A.E. Brouwer Strongly regular graphs 1625 P.J. Cameron Strongly regular graphs in: Topics in Algebraic Graph Theory, L.W. Beineke and R.J. Wilson eds., Cambridge University Press 203-221 (2004) 1626 A.E. Brouwer Classification of small (0,2)-graphs J. Combin. Th. (A) 113 1636-1645 (2006) 1627 N.B. Limaye, D.G. Sarvate, P. Stanica, P.T. Young Regular and strongly regular planar graphs J. Comb. Math. Comb. Comput. 54 111-127 (2005) 1628 J. Diaz, M. Karminski Max-Cut and Max-Bisection are NP-hard on unit disk graphs Theo. Comp. Sci 377 271-276 (2007) 1629 H.L. Bodlaender, K. Jansen On the complexity of the maximum cut problem Nordic J. Comput. 7 No.1 14-31 (2000) 1630 M. Yannakakis Node- and edge-deletion NP-complete problems Proceedings of the tenth anual ACM Symposium on Theory of Computing (STOC'78) 253-264 (1978) 1631 M. Yannakakis Node- and edge-deletion NP-complete problems Proceedings of the tenth anual ACM Symposium on Theory of Computing (STOC'78) 253-264 (1978) 1632 J. Blazewicz, M. Kasprzak, B. Leroy-Beaulieu, D. de Werra Finding Hamiltonian circuits in quasi-adjoint graphs Discrete Appl. Math. 156 2573-2580 (2008) doi 10.1016/j.dam.2008.03.014 1633 J. Blazewicz, M. Kasprzak Reduced-by-matching graphs: toward simplifying Hamiltonian circuit problem Fundamenta Informatica 118 225-244 (2012) 1634 N. Apollonio, P.G. Franciosa A characterization of partial directed line graphs Discrete Math. 307 2598 2614 (2007) 1635 D. Lokshantov, M. Vatshelle, Y. Villanger Independent set in P5-free graphs in polynomial time Accepted for publication 1636 S. Chaplick, T. Ueckerdt Planar graphs as VPG-Graphs Journal of Graph Algorithms and Applications Vol.17 No.4 475-294 (2013) doi 10.7155/jgaa.00300 JGAA 1637 O. Daescu, A. Kurdia Towards an optimal algorithm for recognizing Laman graphs Journal of Graph Algorithms and Applications Vol.13 No.2 219-232 (2009) doi 10.7155/jgaa.00185 JGAA 1638 S. Kobourov, T. Ueckerdt, K. Verbeek Combinatorial and geometric properties of planar Laman graphs Proc. of the 24th annual ACM-SIAM symposium on Discrete algorithms SODA 2013 1668-1678 (2013) 1639 S. Chaplick, V. Jelinek, J. Kratochvil, T. Vyskocil Bend-bounded path intersection graphs: Sausages, noodles and waffles on a grill Proceedings of WG 2012, Lecture Notes in Computer Science 7551, 274-285 (2012) 1640 By a well-known result of Bollobas and Thomason the number of (4,0)-colorable graphs on n vertices is $2^{\frac{3}{4}\binom{n}{2} + o(n^2)}$. However, it is known that the number of planar graphs on n vertices (and hence the number of co-planar graphs on n vertices) is approximately $c^n n! = 2^{o(n^2)}$ (for a sharp result, see Giménez and Noy). Hence, almost every (4,0)-colorable graph is not co-planar. (Communicated by Andrew Uzzell) 1641 Graphclass: tree. Problem: Clique cover. Tree has no cycles, so each clique is either a single vertex or an edge with both ends. So the Clique cover problem is equivalent to Maximum matching problem (i.e. for any tree T the minimum clique cover size in the sum with maximum matching size is equal to the order of T), which can be solved in linear time using following dynamic programming. Let's consider tree as rooted tree and for each vertex v we denote A(v) the maximum size of matching in subtree of v with some edge adjacent to v and B(v) the maximum size of matching in subtree of v with no edge adjacent to v. Then B(v) = sum (over all sons u of vertex v) max { A(u), B(u) } and A(v) = max (over all sons u of vertex v) B(v) - max { A(u), B(u) } + B(u). Then max{A(r), B(r)}, where r is the root, is the size of maximum matching in the whole tree. (Communicated by Pavel Irzhavski) 1642 By definition, a graph G is maximal clique irreducible if every maximal clique in G contains an edge that is not contained in any other maximal clique. Then, the number of maximal cliques is bounded by m, the number of edges. Thus, the maximal cliques can be obtained in polynomial time (with any algorithm that lists the cliques one by one). This solves the clique and weight clique problems. For the recognition problem, observe that you can return NO if more than m maximal cliques are found by the enumeration algorithm. Otherwise, we just check that every maximal clique has an edge not contained in other maximal cliques. 1643 M.C. Lin, F. Soulignac, J.L. Szwarcfiter Arboricity, h-index and dynamic algorithms Theoret. Comput. Sci. 426 75-90 (2012) doi 10.1016/j.tcs.2011.12.006 1644 J.P. Spinrad Recognizing quasi-triangulated graphs Discrete Appl. Math. 138 No.1-2 203-213 (2004) doi 10.1016/S0166-218X(03)00295-6 1645 M.R. Eguia, F.J. Soulignac Hereditary biclique-Helly graphs: recognition and maximal biclique enumeration DMTCS 15 No.1 (2013) Available here. 1646 M.C. Lin, F. Soulignac, J.L. Szwarcfiter A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs LNCS 5124 355-366 (2008) doi 10.1007/978-3-540-69903-3_32 1647 L.N. Grippo, M.D. Safe On circular-arc graphs having a model with no three arcs covering the circle Anais do XLIV Simpósio Brasileiro de Pesquisa Operacional, 4093-4104 (2012) Available here. 1648 On 2-subdivision graphs we have the following algorithms and reductions: Cutwidth Two homeomorphic graphs G and H have the same cutwidth number: WLOG we can assume that G can be obtained from H by deleting one vertex u of degree 2 and adding a (missing) edge e between u's neighbours v and w. Then if we get a linear layout of G and subdivide edge e by vertex u, placing it in the layout anywhere between v and w we get the same width of all cuts. On the other hand if we have some linear layout of vertices of H, then vertex u is either between v and w or can be moved between them without increasing the width of any cut. And when u is between v and w it can be replaced by an edge e to get a linear layout of G with the same width of all cuts. Since any graph is homeomorphic to its 2-subdivision graph, we get that calculating the cutwidth of a 2-subdivision graph is as hard as calculating the cutwidth of a general graph. Domination To build a dominating set in the 2-subdivision graph G' of graph G we need to include for each vertex v of G its neigbour in G' or the vertex v itself. Since neighbourhoods in graph G' for any two vertices of G are disjont we have that domination number of G' is at least $|V(G)|$. On the other hand a dominating set of size $|V(G)|$ exists consisting of all vertices of G, so the domination number of G' equals $|V(G)|$. Since $|E(G')| = 3|E(G)|$ it follows that the domination number of G' is $|V(G')| - 2|E(G')|$. Feedback vertex set If $G'$ is the 2-subdivision of $G$, then a feedback vertex set of $G$ is also a feedback vertex set of $G'$. And if a feedback vertex set of $G'$ contains a vertex not in $G$, than this vertex can be replaced by a neighbour that is in $G$. Thus, a feedback vertex set in $G'$ can be converted to a feedback vertex set of $G$ of the same size. It follows that $G'$ contains a feedback vertex set of size $k$ iff $G$ does. Note that this reductions maintains planarity and therefore holds for planar 2-subdivions graphs as well. Maximum cut If a graph G has $m$ edges and a maximum cut of size $k$ then the maximum cut size of its 2-subdivistion graph G' is at least $2m + k$: Let G have a cut of size $k$ and let each edge $uv$ be replaced by a path $uxyv$. Then if $uv$ is a cut edge in G, then let all edges $ux$, $xy$ and $yv$ be cut edges in G'. And if $uv$ is not an edge of maximum cut, then let edges $ux$ and $yv$ be edges of the cut in G'. So G' has a cut of size $2m + k$. On the other hand if G' has a cut of size $l$ then for each path $uxyv$ in G' let edge $uv$ be a cut edge if and only if an odd number of the edges $ux$, $xy$, and $yv$ in G' are in the cut. Then a cut exists in G that has size at least $l - 2m$. So the maximum cut problem is NP-complete for 2-subdivision graphs. Hamiltonian cycle A 2-subdivision graph has a Hamiltonian cycle if and only if it is a cycle itself, thus the problem is solvable in linear time. Hamiltonian path A 2-subdivision graph has a Hamiltonian path if and only if it is a cycle or a path, thus the problem is solvable in linear time. Recognition Surely it can be done in linear time. Check every connected component independently, because a graph is a 2-subdivision graph if and only if every connected component is a 2-subdivision graph. 1. If every vertex in the connected componen has degree 2, then this component is a cycle and it is 2-subdivision graph if and only if it has length divisible by 3. 2. If there is at least one vertex of degree non-equal to 2, then we can use one DFS to count lengths of all maximal paths with all non-end vertices of degree 2. The length of every such path should be divisible by 3. This condition is necessary and sufficient. (Communicated by Pavel Irzhavsky) 1649 D.P. Dailey Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete Discrete Math. 30 No.3 289-293 (1980) 1650 L. Stockmeyer Planar 3-colorability is polynomial complete SIGACT News 19-25 (1973) 1651 F.J. Soulignac On proper and Helly circular-arc graphs Ph.D. Thesis Universidad de Buenos Aires (2010) 1652 Let $u,v,w$ be the vertices of a triangle to start the construction of a 3-tree. Attach a vertex y1 to ${u,v,w}$ and y2 to ${u,v,w}$ and y3 to ${u,v,w}$. These are valid 3-tree construction steps and results in a 3-tree with a K3,3 partial subgraph, which is not planar. It follows that planar partial 3-trees are a proper subclass of partial 3-trees. (Communicated by G. Borradaile) 1653 C.H. Papadimitriou, U.V. Vazirani On two geometric problems related to the travelling salesman problem J. of Algorithms 5 No.2 231-246 (1984) 1654 A.E. Feldmann, P. Widmayer An O(n^4) time Algorithm to Compute the Bisection Width of Solid Grid Graphs Proc. of the 19th Annual European Symposium on Algorithms (ESA) (2011) 1655 On star convex graphs we have the following algorithms and reductions: Hamiltonian path Consider any bipartite graph $G = (X, Y, E)$ with $|X| \le |Y|$. Then graph $G' = (X \cup \{x\}, Y \cup \{y\}, E \cup \{(x, z) \forall z \in Y\} \cup \{(x, y)\})$ will be star convex with $T = (X \cup \{x\}, \{(x, z) \forall z \in X\})$. It is easy to see now that if $G$ has Hamiltonian path $P$ then at least one of its ends is in $Y$ and adding $x$ and $y$ to it we can get Hamiltonian path in $G'$. On the other hand if there is a Hamiltonian path $P'$ in $G'$ then $y$ is one of its ends and its only neighbour $x$ is next to $y$ in $P'$. Removing both $x$ and $y$ we get Hamiltonian path in $G$. Therefore Hamiltonian path problem remains NP-complete for star convex graphs. Hamiltonian cycle Consider any bipartite graph $G = (X, Y, E)$ with $|X| \lt |Y|$. Then graph $G' = (X \cup \{x\}, Y, E \cup \{(x, z) \forall z \in Y\})$ will be star convex with $T = (X \cup \{x\}, \{(x, z) \forall z \in X\})$ and $G'$ has Hamiltonian cycle if and only if G has Hamiltonian path. Consider any bipartite graph $G = (X, Y, E)$ with $|X| = |Y|$. Then graph $G' = (X \cup \{x, u\}, Y \cup \{y, v\}, E \cup \{(x, z) \forall z \in Y\} \cup \{(z, y) \forall z \in X\} \cup \{(x, y), (u, y), (x, v), (u, v))$ is tree convex with $T = (X \cup \{x, u\}, \{(x, z) \forall z \in X \cup \{u\}\})$ and has Hamiltonian cycle if and only if $G$ has Hamiltonian path. Therefore Hamiltonian cycle problem remains NP-complete for star convex graphs. Recognition Linear. Graph $G = (X, Y, E)$ is star convex if and only if there exists vertex $x \in X$ such that $(x, y) \in E$ for all $y \in Y \mid \deg(y) \ge 2$. If there is such $x$, then $x$ can be center of star $T$. If there is no such $x$ then for any center $z$ of star $T$ there exists vertex $y \in Y$ such that it is adjacent to two leaves of $T$, but not adjacent to the center of $T$. (P. Irzhavsky) 1656 It is easy to see that $H_{n,q}$ graph doesn't have Hamiltonian path (and therefore cycle) for $n \ge 3$ since in case of existance of Hamiltonian path the outer cycle with exception of at most one edge should be part of this path because of vertices of degree 2. But there are at least 4 inner vertices that should be ends of path or be adjacent in Hamiltonian path with vertices of outer cycle. In case n = 2 graph is a simple cycle and in case n = 1 graph has only one vertex. Both cases are trivial, so the problems are linear time solvable. Recognition is also linear. Cases of n = 1 (single vertex) and n = 2 (simple cycle of length 12q) are trivial, so let n be at least 3. It is easy to see that graph $H_{n,q}$ has 6qn(n-1) edges. Consider maximal paths with non-end vertices of degree 2. All of them can be found using one DFS. The longest such path has 6q edges. So now both n and q are known (since equation n(n-1) = a has at most one positive integer root). Now we can try to extract all vertices of $H_{n,q}$ from the given graph, moving diagonal wave from one corner to the other. For the $F_n$ grids similar arguments apply. (P. Irzhavsky) 1657 J. Hopcroft, R. Tarjan Efficient algorithms for graph manipulation C.ACM 16 No.6 372-378 (1973) 1658 W.-k. Shih, S. Wu, Y.S. Kuo Unifying Maximum Cut and Minimum Cut of a Planar Graph IEEE Transactions on Computer 39 No.5 694-697 (1990) 1659 If, in the notation of [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) , the intersection graph H of (C,co-A) is not chordal, then there are three arcs co-A_1, co-A_2 and co-A_3 in co-A corresponding to three consecutive vertices of some chordless cycle of length at least 4 in H and, consequently, A_1, A_2 and A_3 together cover the circle. Therefore, a model not having three arcs covering the circle satisfies (i) and (ii) of Theorem 1 of [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) and, hence, it is Helly. To see that it is also normal (i.e., has no two arcs covering the circle) is much eaiser: if one is forced to cover the circle with two arcs, then the graph has at least three vertices and so in any model of such a graph if there were two arcs covering the circle then there would be also three arcs covering the circle. Similar reasoning applies to proper Helly circular-arc and unit Helly circular arc graphs. (M.D. Safe) 1660 Consider an arbitrary 2-connected, cubic, planar graph $G$ and an edge $uv$ of $G$. At first let's replace edge $uv$ by vertices $a, b, x, y$ and edges $\{u, a\}, \{a, x\}, \{a, y\}, \{x, b\}, \{y, b\}, \{b, v\}$. Replace $x$ and $y$ by diamond s $X$ and $Y$, respectively: $x$ is replaced by $x_1, x_2, x_3, x_4$, edges $\{a, x\}, \{x, b\}$ are replaced by $\{a, x_1\}, \{x_2, b\}$ and the edges $\{x_1, x_3\}, \{x_1, x_4\}, \{x_3, x_4\}, \{x_3, x_2\}, \{x_4, x_2\}$ are added. And the same for $y$. Now any Hamiltonian path in the resulting graph $H$ starts with either the vertices of $X$ or the vertices of $Y$. Without loss of generality, assume it starts with the vertices of $X$. The path is of one of the forms $X,a,Y,b,v,\dots,u$; or $X,b,Y,a,u,\dots,v$; or $X,b,v,\dots,u,a,Y$; or $X,a,u,\dots,v,b,Y$. Hence a Hamiltonian path in $H$ exists iff $G$ has a Hamiltonian cycle with edge $uv$. (P. Irzhavsky) 1661 M. Conforti, G. Cornuejols, K. Vuskovic Decomposition of odd-hole-free graphs by double star cutsets and 2-joins Discrete Appl. Math. 141 No.1-3 41-91 (2004) 1662 M.V.G. da Silva, K. Vuskovic Decomposition of even-hole-free graphs with star cutsets and 2-joins J. of Combin. Th. (B) 103 No.1 144-183 (2013) 1663 M. Kaminski, V. Lozin Vertex 3-colorability of claw-free graphs Algorithmic Operations Research Vol.2 15-21 (2007) 1664 J. Mycielski Sur le coloriage des graphes Colloq. Math. 3 161-162 1665 V. Lozin, M. Milanic On the Maximum Independent Set Problem in Subclasses of Planar Graphs Journal of Graph Algorithms and Applications Vol.14 No.2 269-286 (2010) doi 10.7155/jgaa.00207 JGAA 1666 I.E. Zverovich, O.I. Zverovich Independent Domination in hereditary classes Theoretical Comp. Sci. 352 215-225 (2006) doi 10.1016/j.tcs.2005.10.049 1667 P. ZhangM.Sc. Thesis, University of British Columbia If $G$ and $G'$ have the same P4 -structure, then $G$ is $P_4$-bipartite iff $G'$ is. Hence, if $C$ is a subclass of $P_4$-bipartite, then so is the class $C$-perfect. (Communicated by J. Nastos) 1668 I.E. Zverovich Satgraphs and independent Domination. Part 1 Theoretical Comp. Sci. 352 47-56 (2006) doi 10.1016/j.tcs.2005.08.038 1669 M. Farber Independent domination in chordal graphs Operations Research Lett. 1 No.4 134-138 (1982) doi 10.1016/0167-6377(82)90015-3 1670 A. Gyarfas Generalized split graphs and Ramsey numbers J. of Combin. Th. (A) 81 255-261 (1998) 1671 D.V. Andrade, L.H. de Figueiredo Good Approximations for the Relative Neighbourhood Graph Proc. of the 13th Canadian Conference on Computation Geometry CCCG'01 25-28 (2001) 1672 J.W. Jaromczyk, G.T. Toussaint Relative Neighborhood Graphs and Their Relatives Proc. of the IEEE 80 No.9 1502-1517 (1992) 1673 A. Lubiw Visibility graphs, dismantlability and the cops-and-robbers game Workshop on Graphs and Algorithms, Fields Institute, May 5-6 (2014) 1674 H.-C. Chang, H.-I. Lu A faster algorithm to recognize even-hole-free graphs Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12), 1286-1297, (2012) 1675 Proof on stackexchange (M. De Biasi) 1676 M. Kaminski Max-cut and containment relations in graphs Proceedings of WG 2010, Lecture Notes in Computer Science 6410, 15-26 (2010) 1677 F. Barahona The max-cut problem on graphs not contractible to $K_5$ Oper. Res. Lett. 2 No.3 107-111 (1983) 1678 V. Guruswami Maximum cut on line and total graphs Discrete Appl. Math. 92 217-221 (1999) doi 10.1016/S0166-218X(99)00056-6 1679 M.-S. Chang, L.-J. Hung Recognition of probe ptolemaic graphs Proceedings of IWOCA 2010 LNCS 6460 286-290 (2011) 1680 Y. Nussbaum Recognition of probe proper interval graphs Discrete Appl. Math. 167 228-238 (2014) 1681 M.-S. Chang, L.-J. Hung, P. Rosssmanith Recognition of probe distance-hereditary graphs Discrete Appl. Math. 161 336-348 (2013) 1682 G. Di Stefano Distance-hereditary comparability graphs Discrete Appl. Math. 160 2669-2680 (2012) 1683 C.-M. Lee, M.-S. Chang Distance-hereditary graphs are clique-perfect Discrete Appl. Math. 154 525-536 (2006) 1684 J. Hopcroft, J. Wong Linear time algorithm for the isomorphism of planar graphs Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, 172-184 (1974) doi 10.1145/800119.803896 1685 H. Bodlaender Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees J. Algorithms 11 No.4 631-643 (1990) doi 10.1016/0196-6774(90)90013-5 1686 I.S. Filotti, J.N. Mayer A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing STOC'80 236-243 (1980) doi 10.1145/800141.804671 1687 G. Miller Isomorphism testing for graphs of bounded genus Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing STOC'80 225-235 (1980) doi 10.1145/800141.804670 1688 V.N. Zemlyachenko, N.M. Korneenko, R.I. Tyshkevich Graph isomorphism problem J. of Soviet Mathematics 29 No.4 1426-1481 doi 10.1007/BF02104746 1689 R. Uehara, S. Toda, T. Nagoya Graph isomorphism completenes for chordal bipartite graphs and strongly chordal graphs Discrete Appl. Math. 145 No.3 479-482 doi 10.1016/j.dam.2004.06.008 1690 S. Kratsch, P. Schweitzer Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs Proceedings of WG 2012, Lecture Notes in Computer Science 7551, 34-45 (2012) 1691 E.M. Luks Isomorphism of graphs of bounded valence can be tested in polynomial time Journal of Computer and System Sciences 25 42-65 (1982) doi 10.1016/0022-0000(82)90009-5 1692 H.J. Broersma, H.J. Veldman Restrictions on induced subgraphs ensuring Hamiltonicity or pancyclicity of $K_{1,3}$-free graphs Contemporary methods in graph theory, BI-Wiss.-Verl. 181-194 (199) 1693 R. Faudree, E. Flandrin, Z. Ryjacek Claw-free graphs - a survey Discrete Math. 164 87-147 (1997) doi 10.1016/S0012-365X(96)00045-3 1694 Since every 2-connected (P6 ,claw )-free graph is hamiltonian and every hamiltonian graph is 2-connected, it is straightforward to check whether a (P6 ,claw )-free graph has a Hamiltonian cycle. (Communicated by S.-i. Oum) 1695 F.R.K. Chung On the cutwidth and the topological bandwidth of a tree SIAM J. Alg. Discr. Meth. 6 1985 268--277 1696 F.R.K. Chung, P.D. Seymour Graphs with small bandwidth and cutwidth Disc. Math. 75 1989 113--119 1697 E. DeLaVina, B. Waller A NOTE ON A CONJECTURE OF HANSEN ET AL. manuscript 2009 http://cms.dt.uh.edu/faculty/delavinae/research/DelavinaWaller2009.pdf 1698 D.J. Kleitman, D.B. West Spanning trees with many leaves SIAM J. Alg. Discr. Meth. 4 1991 99--106 1699 R. Sasák Comparing 17 graph parameters Master's thesis, University of Bergen 2010