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:
|
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:
|
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]
, 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
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)
[1327]
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.
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) 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. Zhang A study on generalized solution concept in constraint satisfaction and group colouring M.Sc. Thesis, University of British Columbia (2014) 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 |