Graphclass: B_k-VPG

The speed of a class $X$ is the function $n \mapsto |X_n|,ドル where $X_n$ is the set of $n$-vertex labeled graphs in $X$.

Depending on the rate of growths of the speed of the class, ISGCI distinguishes the following values of the parameter:
Constant
Polynomial
Exponential
Factorial
Superfactorial (2ドル^{o(n^2)}$ )
Superfactorial (2ドル^{\Theta(n^2)}$ )

V.E. Alekseev
Range of values of entropy of hereditary classes of graphs
Diskretn. Math. 4:2 148-157 (1995)

B. Bollobas, A. Thomason
Projections of bodies and hereditary properties of hypergraphs
Bull. London Math. Soc. 27(5) 417-424 (1995)

The acyclic chromatic number of a graph $G$ is the smallest size of a vertex partition $\{V_1,\dots,V_l\}$ such that each $V_i$ is an independent set and for all $i,j$ that graph $G[V_i\cup V_j]$ does not contain a cycle.

The bandwidth of a graph $G$ is the shortest maximum "length" of an edge over all one dimensional layouts of $G$. Formally, bandwidth is defined as $\min_{i \colon V \rightarrow \mathbb{N}\;}\{\max_{\{u,v\}\in E\;} \{|i(u)-i(v)|\}\mid i\text{ is injective}\}$.

(no preview available)

(no preview available)

A book embedding of a graph $G$ is an embedding of $G$ on a collection of half-planes (called pages) having the same line (called spine) as their boundary, such that the vertices all lie on the spine and there are no crossing edges. The book thickness of a graph $G$ is the smallest number of pages over all book embeddings of $G$.

F. Bernhart, P.C. Kainen
The book thickness of a graph
J. of Combin. Th. (B) 27 320-331 (1979)

Consider the following decomposition of a graph $G$ which is defined as a pair $(T,L)$ where $T$ is a binary tree and $L$ is a bijection from $V(G)$ to the leaves of the tree $T$. The function $\text{cut-bool} \colon 2^{V(G)} \rightarrow R$ is defined as $\text{cut-bool}(A)$ := $\log_2|\{S \subseteq V(G) \backslash A \mid \exists X \subseteq A \colon S = (V(G) \backslash A) \cap \bigcup_{x \in X} N(x)\}|$. Every edge $e$ in $T$ partitions the vertices $V(G)$ into $\{A_e,\overline{A_e}\}$ according to the leaves of the two connected components of $T - e$. The booleanwidth of the above decomposition $(T,L)$ is $\max_{e \in E(T)\;} \{ \text{cut-bool}(A_e)\}$. The booleanwidth of a graph $G$ is the minimum booleanwidth of a decomposition of $G$ as above.

A branch decomposition of a graph $G$ is a pair $(T,\chi),ドル where $T$ is a binary tree and $\chi$ is a bijection, mapping leaves of $T$ to edges of $G$. Any edge $\{u, v\}$ of the tree divides the tree into two components and divides the set of edges of $G$ into two parts $X, E \backslash X,ドル consisting of edges mapped to the leaves of each component. The width of the edge $\{u,v\}$ is the number of vertices of $G$ that is incident both with an edge in $X$ and with an edge in $E \backslash X$. The width of the decomposition $(T,\chi)$ is the maximum width of its edges. The branchwidth of the graph $G$ is the minimum width over all branch-decompositions of $G$.

Consider a decomposition $(T,\chi)$ of a graph $G$ where $T$ is a binary tree with $|V(G)|$ leaves and $\chi$ is a bijection mapping the leaves of $T$ to the vertices of $G$. Every edge $e \in E(T)$ of the tree $T$ partitions the vertices of the graph $G$ into two parts $V_e$ and $V \backslash V_e$ according to the leaves of the two connected components in $T - e$. The width of an edge $e$ of the tree is the number of edges of a graph $G$ that have exactly one endpoint in $V_e$ and another endpoint in $V \backslash V_e$. The width of the decomposition $(T,\chi)$ is the largest width over all edges of the tree $T$. The carvingwidth of a graph is the minimum width over all decompositions as above.

The chromatic number of a graph is the minimum number of colours needed to label all its vertices in such a way that no two vertices with the same color are adjacent.

The cliquewidth of a graph is the number of different labels that is needed to construct the graph using the following operations:

• creation of a vertex with label $i,ドル
• disjoint union,
• renaming labels $i$ to label $j,ドル and
• connecting all vertices with label $i$ to all vertices with label $j$.

J.A. Makowsky, U. Rotics
On the clique-width of graphs with few $P_4$'s.
International Journal of Foundations of Computer Science 10 (1999) 329-348

A. Brandstaedt, V.V. Lozin
On the linear structure and clique-width of bipartite permutation graphs.
Accepted for Ars Combinatorica

B. Courcelle, S. Olariu
Upper bounds to the clique-width of graphs.
Discrete Appl. Math. 101 (2000) 77-114

Golumbic, Martin Charles; Rotics, Udi
On the clique-width of perfect graph classes (extended abstract) .
Graph theoretic concepts in computer science. 25th international workshop, WG '99 Ascona, Switzerland, June 17-19, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1665, 135-147 (1999)

Golumbic, Martin Charles; Rotics, Udi
On the clique-width of perfect graph classes (extended abstract) .
Graph theoretic concepts in computer science. 25th international workshop, WG '99 Ascona, Switzerland, June 17-19, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1665, 135-147 (1999)

N. Korpelainen, V.V. Lozin, C. Mayhill
Split permutation graphs
Graphs and Combinatorics 30 633-646 (2014)

B. Courcelle, S. Olariu
Upper bounds to the clique-width of graphs.
Discrete Appl. Math. 101 (2000) 77-114

J.A. Makowsky, U. Rotics
On the clique-width of graphs with few $P_4$'s.
International Journal of Foundations of Computer Science 10 (1999) 329-348

Golumbic, Martin Charles; Rotics, Udi
On the clique-width of perfect graph classes (extended abstract) .
Graph theoretic concepts in computer science. 25th international workshop, WG '99 Ascona, Switzerland, June 17-19, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1665, 135-147 (1999)

The cochromatic number of a graph $G$ is the minimum number of colours needed to label all its vertices in such a way that that every set of vertices with the same colour is either independent in G, or independent in $\overline{G}$.

(no preview available)

The cutwidth of a graph $G$ is the smallest integer $k$ such that the vertices of $G$ can be arranged in a linear layout $v_1, \ldots, v_n$ in such a way that for every $i = 1, \ldots,n - 1,ドル there are at most $k$ edges with one endpoint in $\{v_1, \ldots, v_i\}$ and the other in $\{v_{i+1}, \ldots, v_n\}$.

Let $G$ be a graph and consider the following algorithm:

• Find a vertex $v$ with smallest degree.
• Delete vertex $v$ and its incident edges.
• Repeat as long as the graph is not empty.

The degeneracy of a graph $G$ is the maximum degree of a vertex when it is deleted in the above algorithm.

The diameter of a graph $G$ is the length of the longest shortest path between any two vertices in $G$.

(no preview available)

The distance to block of a graph $G$ is the size of a smallest vertex subset whose deletion makes $G$ a block graph.

(no preview available)

Let $G$ be a graph. Its distance to clique is the minimum number of vertices that have to be deleted from $G$ in order to obtain a clique.

A cluster is a disjoint union of cliques. The distance to cluster of a graph $G$ is the size of a smallest vertex subset whose deletion makes $G$ a cluster graph.

The distance to co-cluster of a graph is the minimum number of vertices that have to be deleted to obtain a co-cluster graph.

The distance to cograph of a graph $G$ is the minimum number of vertices that have to be deleted from $G$ in order to obtain a cograph .

(no preview available)

The distance to linear forest of a graph $G = (V, E)$ is the size of a smallest subset $S$ of vertices, such that $G[V \backslash S]$ is a disjoint union of paths and singleton vertices.

The distance to outerplanar of a graph $G = (V,E)$ is the minumum size of a vertex subset $X \subseteq V,ドル such that $G[V \backslash X]$ is a outerplanar graph.

The genus $g$ of a graph $G$ is the minimum number of handles over all surfaces on which $G$ can be embedded without edge crossings.

The max-leaf number of a graph $G$ is the maximum number of leaves in a spanning tree of $G$.

The parameter maximum clique of a graph $G$ is the largest number of vertices in a complete subgraph of $G$.

The maximum degree of a graph $G$ is the largest number of neighbors of a vertex in $G$.

(no preview available)

An independent set of a graph $G$ is a subset of pairwise non-adjacent vertices. The parameter maximum independent set of graph $G$ is the size of a largest independent set in $G$.

For a graph $G = (V,E)$ an induced matching is an edge subset $M \subseteq E$ that satisfies the following two conditions: $M$ is a matching of the graph $G$ and there is no edge in $E \backslash M$ connecting any two vertices belonging to edges of the matching $M$. The parameter maximum induced matching of a graph $G$ is the largest size of an induced matching in $G$.

A matching in a graph is a subset of pairwise disjoint edges (any two edges that do not share an endpoint). The parameter maximum matching of a graph $G$ is the largest size of a matching in $G$.

A clique cover of a graph $G = (V, E)$ is a partition $P$ of $V$ such that each part in $P$ induces a clique in $G$. The minimum clique cover of $G$ is the minimum number of parts in a clique cover of $G$. Note that the clique cover number of a graph is exactly the chromatic number of its complement.

A dominating set of a graph $G$ is a subset $D$ of its vertices, such that every vertex not in $D$ is adjacent to at least one member of $D$. The parameter minimum dominating set for graph $G$ is the minimum number of vertices in a dominating set for $G$.

(no preview available)

A path decomposition of a graph $G$ is a pair $(P,X)$ where $P$ is a path with vertex set $\{1, \ldots, q\},ドル and $X = \{X_1,X_2, \ldots ,X_q\}$ is a family of vertex subsets of $V(G)$ such that:

• $\bigcup_{p \in \{1,\ldots ,q\}} X_p = V(G)$
• $\forall\{u,v\} \in E(G) \exists p \colon u, v \in X_p$
• $\forall v \in V(G)$ the set of vertices $\{p \mid v \in X_p\}$ is a connected subpath of $P$.

The width of a path decomposition $(P,X)$ is max$\{|X_p| - 1 \mid p \in \{1,\ldots ,q\}\}$. The pathwidth of a graph $G$ is the minimum width among all possible path decompositions of $G$.

Let $M$ be the $|V| \times |V|$ adjacency matrix of a graph $G$. The cut rank of a set $A \subseteq V(G)$ is the rank of the submatrix of $M$ induced by the rows of $A$ and the columns of $V(G) \backslash A$. A rank decomposition of a graph $G$ is a pair $(T,L)$ where $T$ is a binary tree and $L$ is a bijection from $V(G)$ to the leaves of the tree $T$. Any edge $e$ in the tree $T$ splits $V(G)$ into two parts $A_e, B_e$ corresponding to the leaves of the two connected components of $T - e$. The width of an edge $e \in E(T)$ is the cutrank of $A_e$. The width of the rank-decomposition $(T,L)$ is the maximum width of an edge in $T$. The rankwidth of the graph $G$ is the minimum width of a rank-decomposition of $G$.

A tree depth decomposition of a graph $G = (V,E)$ is a rooted tree $T$ with the same vertices $V,ドル such that, for every edge $\{u,v\} \in E,ドル either $u$ is an ancestor of $v$ or $v$ is an ancestor of $u$ in the tree $T$. The depth of $T$ is the maximum number of vertices on a path from the root to any leaf. The tree depth of a graph $G$ is the minimum depth among all tree depth decompositions.

A tree decomposition of a graph $G$ is a pair $(T, X),ドル where $T = (I, F)$ is a tree, and $X = \{X_i \mid i \in I\}$ is a family of subsets of $V(G)$ such that

• the union of all $X_i,ドル $i \in I$ equals $V,ドル
• for all edges $\{v,w\} \in E,ドル there exists $i \in I,ドル such that $v, w \in X_i,ドル and
• for all $v \in V$ the set of nodes $\{i \in I \mid v \in X_i\}$ forms a subtree of $T$.

The width of the tree decomposition is $\max |X_i| - 1$.
The treewidth of a graph is the minimum width over all possible tree decompositions of the graph.

Let $G$ be a graph. Its vertex cover number is the minimum number of vertices that have to be deleted in order to obtain an independent set.

J. Diaz, M. Penrose, J. Petit, M. Serna
Approximating layout problems on random geometric graphs
Journal of Algorithms 39 78-117 (2001)

B. Monien, I.H. Sudborough
Min cut is NP-complete for edge weighted trees
Theoretical Comp. Sci. 58 Issue 1-3, 209-229 (1988)

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)

J. Diaz, M. Penrose, J. Petit, M. Serna
Approximating layout problems on random geometric graphs
Journal of Algorithms 39 78-117 (2001)

H.L. Bodlaender, D.M. Thilikos
Treewidth for graphs with small chordality
Discrete Appl. Math. 79 1997 45--61

S. Arnborg, D.G. Corneil, A. Proskurowski
Complexity of finding embeddings in a $k$--tree
SIAM J. Alg. Discr. Meth. 8 1987 277--284

H.L. Bodlaender
A tourist guide through treewidth
Acta Cybernetica 11 1993 1--23

D.P. Dailey
Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
Discrete Math. 30 No.3 289-293 (1980)

Z. Deniz, E. Galby, A. Munaro, B. Ries
On contact graphs of paths on a grid
Proc. of Graph Drawing 2018, LNCS 11282 317-330 (2018)

D. Cavallaro
Hamiltonicity and the computational complexity of graph problems
Bachelor Thesis, TU Berlin (2019)

M.R. Garey, D.S. Johnson
Computers and Intractability -- A Guide to the Theory of \NP--completeness
Freeman and Company, San Francisco 1979

A. Graef, M. Stumpf, G. Weissenfels
On coloring unit disk graphs
Algorithmica 20 277-293 (1998)

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)

M. Middendorf, F. Pfeiffer
The max clique problem in classes of string-graphs
Discrete Math. 108 365-372 (1992)

J. Kratochvil, A. Kubena
On intersection representations of co-planar graphs
Discrete Math. 178 No.1-3 251-255 (1998)

S. Cabello, J. Cardinal, S. Langerman
The clique problem in ray intersection graphs
Discrete and computational Geom. 50 771-783 (2013)

N. Champseix, E. Galby, A. Munaro, B. Ries
CPG graphs: Some structural and hardness results
Discrete Appl. Math 290 17-35 (2021)

D. Kral, J. Kratochvil, Z. Tuza, G.J. Woeginger
Complexity of coloring graphs without forbidden induced subgraphs
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 254-262 (2001)

H. Imai, T. Asano
Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
J. Algorithms 4 1983 310--323

J.M. Keil, L. Stewart
Approximating the minimum cover and other hard problems in subtree filament graphs
Discrete Appl. Math. 154 1983-1995 (2006)

M.R. Cerioli, L. Faria, T.O. Ferreira, C.A.J. Martinhon, F. Protti, B. Reed
Partition into cliques for cubic graphs: Planar case, complexity and approximation
Discrete Appl. Math. 156 No.12 2270-2278 (2008)

M.R. Cerioli, F. Luerbio, O. Talita, F. Protti
A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
RAIRO-Theor. Inf. Appl. 45 No.3, 331-346 (2011)

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)

F. Gavril
Intersection graphs of Helly families of subtrees
Discrete Appl. Math. 66 1996 45--56

H. Imai, T. Asano
Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
J. Algorithms 4 1983 310--323

M.R. Garey, D.S. Johnson, G.L. Miller, C.H. Papadimitriou
The complexity of coloring circular arcs and chords
SIAM J. on Algebraic and Discrete Methods 1 No.2 216-227 (1980)

M.R. Garey, D.S. Johnson, G.L. Miller, C.H. Papadimitriou
The complexity of coloring circular arcs and chords
SIAM J. on Algebraic and Discrete Methods 1 No.2 216-227 (1980)

M.R. Garey, D.S. Johnson
Computers and Intractability -- A Guide to the Theory of \NP--completeness
Freeman and Company, San Francisco 1979

A. Graef, M. Stumpf, G. Weissenfels
On coloring unit disk graphs
Algorithmica 20 277-293 (1998)

B.N. Clark, C.J. Colbourn, D.S. Johnson
Unit disk graphs
Discrete Math. 86 1990 165--177

I.E. Zverovich, V.E. Zverovich
An induced subgraph characterization of domination perfect graphs
J. Graph Theory 20 1995 375--395

K.S. Booth, J.H. Johnson
Dominating sets in chordal graphs
SIAM J. Comput. 11 (1982) 191-199

J.M. Keil
The complexity of domination problems in circle graphs
Discrete Appl. Math. 42 (1993) 51-63

(no preview available)

B.N. Clark, C.J. Colbourn, D.S. Johnson
Unit disk graphs
Discrete Math. 86 1990 165--177

Berman, Fran; Johnson, David; Leighton, Tom; Shor, Peter W.; Snyder, Larry
Generalized planar matching.
J. Algorithms 11, No.2, 153-184 (1990)

D.S. Johnson
The \NP--completeness column: an ongoing guide
J. Algorithms 6 145--159, 291--305, 434--451 1985

M.R. Cerioli, F. Luerbio, O. Talita, F. Protti
A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
RAIRO-Theor. Inf. Appl. 45 No.3, 331-346 (2011)

M.R. Garey, D.S. Johnson
Computers and Intractability -- A Guide to the Theory of \NP--completeness
Freeman and Company, San Francisco 1979

A.A. Bertossi
Dominating sets for split and bipartite graphs.
Inform. Process. Lett. 19 (1984) 37-40

D.G. Corneil, Y. Perl
Clustering and domination in perfect graphs.
Discrete. Appl. Math. 9 (1984) 27-39

K.S. Booth, J.H. Johnson
Dominating sets in chordal graphs
SIAM J. Comput. 11 (1982) 191-199

B.N. Clark, C.J. Colbourn, D.S. Johnson
Unit disk graphs
Discrete Math. 86 1990 165--177

(no preview available)

D. Cavallaro
Hamiltonicity and the computational complexity of graph problems
Bachelor Thesis, TU Berlin (2019)

(no preview available)

A. Takaoka, S. Tayu, S. Ueno
On minimum feedback vertex set in graphs
Third Internation Conference on Networking and Computing 429-434 (2012)

A. Munaro
On line graphs of subcubic triangle-free graphs
Discrete Math. 340 No.6 1210-1226 (2017)

M.R. Garey, D.S. Johnson
Computers and Intractability -- A Guide to the Theory of \NP--completeness
Freeman and Company, San Francisco 1979

E. Speckenmeyer
On feedback vertex sets and nonseparating independent sets in cubic graphs
J. of Graph Theory 12 No.3 405-412 (1988)

V.N. Zemlyachenko, N.M. Korneenko, R.I. Tyshkevich
Graph isomorphism problem
J. of Soviet Mathematics 29 No.4 1426-1481

F.R.K. Chung
On the cutwidth and the topological bandwidth of a tree
SIAM J. Alg. Discr. Meth. 6 1985 268--277

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

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)

C. Picouleau
Complexity of the Hamiltonian cycle in regular graph problem
Theoret. Comput. Sci. 131 463-473 (1994)

C. Picouleau
Complexity of the Hamiltonian cycle in regular graph problem
Theoret. Comput. Sci. 131 463-473 (1994)

A. Munaro
On line graphs of subcubic triangle-free graphs
Discrete Math. 340 No.6 1210-1226 (2017)

(no preview available)

T. Akiyama, T. Nishizeki, N. Saito
NP-completeness of the Hamiltonian cycle problem for bipartite graphs
J. Inf. Process. V.3 73-76 (1980)

A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter
Hamiltonian paths in grid graphs
SIAM J. Comput. Vol.11 No.4 676-686 (1982)

C.J. Colbourn, L.K. Stewart
Dominating cycles in series-parallel graphs
Ars Combin. 19A 107-112 (1985)

P. Damaschke
The Hamiltonian circuit problem for circle graphs is NP-complete
Information Proc. Lett. 32 No.1 1-2 (1989)

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)

C. Picouleau
Complexity of the Hamiltonian cycle in regular graph problem
Theoret. Comput. Sci. 131 463-473 (1994)

B.S. Panda, D. Pradhan
NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs
Manuscript

A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter
Hamiltonian paths in grid graphs
SIAM J. Comput. Vol.11 No.4 676-686 (1982)

B.N. Clark, C.J. Colbourn, D.S. Johnson
Unit disk graphs
Discrete Math. 86 1990 165--177

A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter
Hamiltonian paths in grid graphs
SIAM J. Comput. Vol.11 No.4 676-686 (1982)

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)

E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys
The Traveling Salesman Problem
J. Wiley, New York 1990

G. Narasimhan
A note on the Hamiltonian Circuit Problem on directed path graphs
Information Proc. Lett. 32 No.4 167-170 (1989)

M.C. Golumbic
Algorithmic Graph Theory and Perfect Graphs
Academic Press, New York 1980

H. Mueller
Hamiltonian circuits in chordal bipartite graphs
Discrete Math. 156 291-298 (1996)

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)

A.A. Bertossi, M.A. Bonuccelli
Hamiltonian Circuits in interval graph generalizations
Information Proc. Lett. 23 195-200 (1986)

(no preview available)

C. Picouleau
Complexity of the Hamiltonian cycle in regular graph problem
Theoret. Comput. Sci. 131 463-473 (1994)

C. Picouleau
Complexity of the Hamiltonian cycle in regular graph problem
Theoret. Comput. Sci. 131 463-473 (1994)

A. Munaro
On line graphs of subcubic triangle-free graphs
Discrete Math. 340 No.6 1210-1226 (2017)

(no preview available)

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)

C. Picouleau
Complexity of the Hamiltonian cycle in regular graph problem
Theoret. Comput. Sci. 131 463-473 (1994)

A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter
Hamiltonian paths in grid graphs
SIAM J. Comput. Vol.11 No.4 676-686 (1982)

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)

G. Narasimhan
A note on the Hamiltonian Circuit Problem on directed path graphs
Information Proc. Lett. 32 No.4 167-170 (1989)

H. Mueller
Hamiltonian circuits in chordal bipartite graphs
Discrete Math. 156 291-298 (1996)

A.A. Bertossi, M.A. Bonuccelli
Hamiltonian Circuits in interval graph generalizations
Information Proc. Lett. 23 195-200 (1986)

I.E. Zverovich, V.E. Zverovich
An induced subgraph characterization of domination perfect graphs
J. Graph Theory 20 1995 375--395

I.E. Zverovich
Satgraphs and independent Domination. Part 1
Theoretical Comp. Sci. 352 47-56 (2006)

J. Kratochvil, J Nesetril
Independent set and clique problems in intersection defined graphs
Commentationes Mathematicae Universitatis Carolinae Vol. 31 No.1 85-93 (1990)

B. Mohar
Face covers and the genus problem for apex graphs
J. Combin. Theory (B), 82(1) 102-117 (2000)

H. Fleischner, G. Sabidussi, V.I. Sarvanov
Maximum independent sets in 3- and 4-regular Hamiltonian graphs
Discrete Math. 310 No.20 2742-2749 (2010)

H. Fleischner, G. Sabidussi, V.I. Sarvanov
Maximum independent sets in 3- and 4-regular Hamiltonian graphs
Discrete Math. 310 No.20 2742-2749 (2010)

N. Champseix, E. Galby, A. Munaro, B. Ries
CPG graphs: Some structural and hardness results
Discrete Appl. Math 290 17-35 (2021)

J. Kratochvil, J Nesetril
Independent set and clique problems in intersection defined graphs
Commentationes Mathematicae Universitatis Carolinae Vol. 31 No.1 85-93 (1990)

C.S. Rim, K. Nakajima
On rectangle intersection and overlap graphs,
IEEE Trans. Circuits Systems/Fund. Theory Appl. 42 549-553, 1995

H. Fleischner, G. Sabidussi, V.I. Sarvanov
Maximum independent sets in 3- and 4-regular Hamiltonian graphs
Discrete Math. 310 No.20 2742-2749 (2010)

M.R. Cerioli, F. Luerbio, O. Talita, F. Protti
A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
RAIRO-Theor. Inf. Appl. 45 No.3, 331-346 (2011)

M.R. Garey, D.S. Johnson, L. Stockmeyer
Some simplified \NP--complete graph problems
Theor. Comp. Sci. 1 1976 237--267

B.N. Clark, C.J. Colbourn, D.S. Johnson
Unit disk graphs
Discrete Math. 86 1990 165--177

(decision variant)

J. Diaz, M. Karminski
Max-Cut and Max-Bisection are NP-hard on unit disk graphs
Theo. Comp. Sci 377 271-276 (2007)

J. Diaz, M. Karminski
Max-Cut and Max-Bisection are NP-hard on unit disk graphs
Theo. Comp. Sci 377 271-276 (2007)

(decision variant)

H.L. Bodlaender, K. Jansen
On the complexity of the maximum cut problem
Nordic J. Comput. 7 No.1 14-31 (2000)

H.L. Bodlaender, K. Jansen
On the complexity of the maximum cut problem
Nordic J. Comput. 7 No.1 14-31 (2000)

R. Adhikary, K. Bose, S. Mukherjee, B. Roy
Complexity of maximum cut on interval graphs
Proc. of 37th International Symposium on Computation Geometry 7:1-7:11 (2021)

H.L. Bodlaender, K. Jansen
On the complexity of the maximum cut problem
Nordic J. Comput. 7 No.1 14-31 (2000)

H.L. Bodlaender, K. Jansen
On the complexity of the maximum cut problem
Nordic J. Comput. 7 No.1 14-31 (2000)

J. Diaz, M. Karminski
Max-Cut and Max-Bisection are NP-hard on unit disk graphs
Theo. Comp. Sci 377 271-276 (2007)

(decision variant)

J. Diaz, G.B. Mertzios
Minimum bisection is NP-hard on unit disk graphs
Mathematical Foundations of Computer Science 2014, LNCS 8635 251-262 (2014)

V.B. Le, R. Nevries
Complexity and algorithms for recognizing polar and monopolar graphs
Theoretical Computer Science 528 1-11 (2014)

V.B. Le, R. Nevries
Complexity and algorithms for recognizing polar and monopolar graphs
Theoretical Computer Science 528 1-11 (2014)

V.B. Le, R. Nevries
Complexity and algorithms for recognizing polar and monopolar graphs
Theoretical Computer Science 528 1-11 (2014)

V.B. Le, R. Nevries
Complexity and algorithms for recognizing polar and monopolar graphs
Theoretical Computer Science 528 1-11 (2014)

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)

Schaefer, Marcus; Stefankovic, Daniel
Decidability of string graphs
J. Comput. Syst. Sci. 68, No.2, 319-334 (2004)

J. Kratochv\'il
String graphs II. Recognizing string graphs is \NP--hard
J. Comb. Theory (B) 52 1991 67--78

(decision variant)

M. Kaminski
Max-cut and containment relations in graphs
Proceedings of WG 2010, Lecture Notes in Computer Science 6410, 15-26 (2010)

M. Kaminski
Max-cut and containment relations in graphs
Proceedings of WG 2010, Lecture Notes in Computer Science 6410, 15-26 (2010)