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