Graphclass: (C₄,P₃,triangle)-free

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
On lower layers of a lattice of hereditary classes of graphs
Diskretn. Anal. Issled. Oper. Ser. 1 4:1 3-12 (1997)

E.R. Scheinerman, J. Zito
On the size of hereditary classes of graphs
J. Combin. Th. B Vol. 61 No.1 16-39 (1994)

J. Balogh, B. Bollobas, D. Weinreich
The speed of hereditary properties of graphs
J. Combin. Th. B Vol. 79 No.2 131-156 (2000)

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.

J. Nesetril, P. Ossona de Mendez
Colorings and homomorphisms of minor closed classes
Discrete and Comput. Geometry 25, The Goodman-Pollack Festschrift 651-664 (2003)

J. Nesetril, P. Ossona de Mendez
Colorings and homomorphisms of minor closed classes
Discrete and Comput. Geometry 25, The Goodman-Pollack Festschrift 651-664 (2003)

J. Nesetril, P. Ossona de Mendez
Colorings and homomorphisms of minor closed classes
Discrete and Comput. Geometry 25, The Goodman-Pollack Festschrift 651-664 (2003)

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}\}$.

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$.

(no preview available)

M. Yannakakis
Embedding planar graph in four pages
Journal of Computer and System Sciences 38 36-67 (1989)

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$.

B. Courcelle, J.A. Makowsky, U. Rotics
Linear time optimization problems on graphs of bounded clique width.
Theory of Computing Systems 33 (2000) 125-150

B. Courcelle, J.A. Makowsky, U. Rotics
Linear time optimization problems on graphs of bounded clique width.
Theory of Computing Systems 33 (2000) 125-150

B. Courcelle, J.A. Makowsky, U. Rotics
Linear time optimization problems on graphs of bounded clique width.
Theory of Computing Systems 33 (2000) 125-150

A. Gy\'arf\'as, D. Kratsch, J. Lehel, F. Maffray
Minimal non--neighbourhood--perfect graphs
J. Graph Theory 21 55--66 1996

R. Boliac, V.V. Lozin
On the clique-width of graphs in hereditary classes.
Rutcor Research Report RRR 14-2002

K. Dabrowski, V. Lozin, R. Raman, B. Ries
Colouring vertices of triangle-free graphs
Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2010, LNCS 6410, 184-195 (2010)

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

B. Courcelle, J.A. Makowsky, U. Rotics
Linear time optimization problems on graphs of bounded clique width.
Theory of Computing Systems 33 (2000) 125-150

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

J.-L. Fouquet
A decomposition for a class of (P_5, \overline{P_5})-free graphs.
Discrete Math. 121 (1993) 19-30

A. Brandstaedt
(P_5,diamond)-free graphs revisited: Structure and linear time optimization.
Accepted for Discrete Appl. Math.

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

J.L. Fouquet, V. Giakoumakis
On semi--$P_4$--sparse graphs
Discrete Math. 165/166 1997 277--300

A. Brandstaedt, D. Kratsch
On the structure of (P_5,gem)-free graphs.
Manuscript 2002

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

A. Brandstaedt, H.-O. Le, R. Mosca
Chordal co-gem-free graphs have bounded clique-width
Manuscript 2002

A. Brandstaedt, K. Klembt, S. Mahfud
P_6- and triangle-free graphs revisited: structure and bounded clique-width
Discrete Math. Theor. Comput. Sci. 8 173-187 (2006)

V. Giakoumakis, J.M. Vanherpe
Linear time recognition and optimization for weak-bisplit graphs, bi-cographs and bipartite P_6-free graphs.
Manuscript, 2001

K. Dabrowski, V. Lozin, R. Raman, B. Ries
Colouring vertices of triangle-free graphs
Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2010, LNCS 6410, 184-195 (2010)

V. Lozin, J. Volz
The clique-width of bipartite graphs in monogenic classes
International J. of Foundations of Comp. Sci. 19 477-494 (2008)

A. Brandstaedt, H.-O. Le, J.M. Vanherpe
Structure and stability number of (chair, co-P, gem)-free graphs.
Manuscript 2001

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

A. Brandstaedt, R. Mosca
On variations of P_4-sparse graphs.
Manuscript 2001

A. Brandstaedt, C.T. Hoang, V.B. Le
Stability number of bull- and chair-free graphs revisited
to appear in Discrete Appl. Math.

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

A. Brandstaedt, C.T. Hoang, V.B. Le
Stability number of bull- and chair-free graphs revisited
to appear in Discrete Appl. Math.

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

V. Lozin, J. Volz
The clique-width of bipartite graphs in monogenic classes
International J. of Foundations of Comp. Sci. 19 477-494 (2008)

A. Brandstaedt, S. Mahfud
Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
Information Processing Letters 84 (2002) 251-259

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

A. Brandstaedt, H.-O. Le, R. Mosca
(gem, co-gem)-free graphs have bounded clique-width
Manuscript 2002

A. Brandstaedt, S. Mahfud
Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
Information Processing Letters 84 (2002) 251-259

V. Lozin, D. Rautenbach
Chordal bipartite graphs of bounded tree- and clique-width.
Rutcor Research Report 2-2003

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)

Lozin, Vadim V.
On a generalization of bi-complement reducible graphs.
Proceedings of MFCS 2000, Lect. Notes Comput. Sci. 1893, 528-538 (2000)

Lozin, Vadim V.
Bipartite graphs without a skew star
Rutcor Research Report RRR 20-2001

J.M. Vanherpe
Clique-width of partner-limited graphs.
International Conference of Graph Theory, Marseille 2000

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

B. Courcelle, J.A. Makowsky, U. Rotics
Linear time optimization problems on graphs of bounded clique width.
Theory of Computing Systems 33 (2000) 125-150

A. Brandstaedt, R. Mosca
On variations of P_4-sparse graphs.
Manuscript 2001

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}$.

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$.

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

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 .

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$.

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$.

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.

T.V. Wimer
Linear algorithms on $k$--terminal graphs
Ph. D. Thesis, {\sl Dept. of Computer Science, URI-030, Clemson Univ., Clemson, SC} 1987

P. Scheffler
The graphs of tree--width $k$ are exactly the partial $k$--trees
manuscript 1986

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.

Input:	A graph G in this class and an integer k.
Output:	True iff the book thickness of G is at most k.

Input:	A graph G in this class.
Output:	An expression that constructs G according to the rules for booleanwidth, using only a constant number of labels. Undefined if this class has unbounded booleanwidth.

Input:	A graph G in this class.
Output:	An expression that constructs G according to the rules for cliquewidth, using only a constant number of labels. Undefined if this class has unbounded cliquewidth.

B. Courcelle, J.A. Makowsky, U. Rotics
Linear time optimization problems on graphs of bounded clique width.
Theory of Computing Systems 33 (2000) 125-150

B. Courcelle, J.A. Makowsky, U. Rotics
Linear time optimization problems on graphs of bounded clique width.
Theory of Computing Systems 33 (2000) 125-150

B. Courcelle, J.A. Makowsky, U. Rotics
Linear time optimization problems on graphs of bounded clique width.
Theory of Computing Systems 33 (2000) 125-150

A. Gy\'arf\'as, D. Kratsch, J. Lehel, F. Maffray
Minimal non--neighbourhood--perfect graphs
J. Graph Theory 21 55--66 1996

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

B. Courcelle, J.A. Makowsky, U. Rotics
Linear time optimization problems on graphs of bounded clique width.
Theory of Computing Systems 33 (2000) 125-150

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

J.-L. Fouquet
A decomposition for a class of (P_5, \overline{P_5})-free graphs.
Discrete Math. 121 (1993) 19-30

A. Brandstaedt
(P_5,diamond)-free graphs revisited: Structure and linear time optimization.
Accepted for Discrete Appl. Math.

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

J.L. Fouquet, V. Giakoumakis
On semi--$P_4$--sparse graphs
Discrete Math. 165/166 1997 277--300

V. Giakoumakis, J.M. Vanherpe
Linear time recognition and optimization for weak-bisplit graphs, bi-cographs and bipartite P_6-free graphs.
Manuscript, 2001

A. Brandstaedt, H.-O. Le, J.M. Vanherpe
Structure and stability number of (chair, co-P, gem)-free graphs.
Manuscript 2001

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

A. Brandstaedt, R. Mosca
On variations of P_4-sparse graphs.
Manuscript 2001

A. Brandstaedt, C.T. Hoang, V.B. Le
Stability number of bull- and chair-free graphs revisited
to appear in Discrete Appl. Math.

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

A. Brandstaedt, C.T. Hoang, V.B. Le
Stability number of bull- and chair-free graphs revisited
to appear in Discrete Appl. Math.

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

A. Brandstaedt, S. Mahfud
Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
Information Processing Letters 84 (2002) 251-259

A. Brandstaedt, S. Mahfud
Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
Information Processing Letters 84 (2002) 251-259

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)

J.M. Vanherpe
Clique-width of partner-limited graphs.
International Conference of Graph Theory, Marseille 2000

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

B. Courcelle, J.A. Makowsky, U. Rotics
Linear time optimization problems on graphs of bounded clique width.
Theory of Computing Systems 33 (2000) 125-150

A. Brandstaedt, R. Mosca
On variations of P_4-sparse graphs.
Manuscript 2001

Corneil, Derek G.; Habib, Michel; Lanlignel, Jean-Marc; Reed, Bruce; Rotics, Udi
Polynomial time recognition of clique-width $\leq 3$ graphs (extended abstract).
Gonnet, Gastón H. (ed.) et al., LATIN 2000: Theoretical informatics. 4th Latin American symposium, Punta del Este, Uruguay, April 10-14, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1776, 126-134 (2000)

Lozin, Vadim V.
On a generalization of bi-complement reducible graphs.
Proceedings of MFCS 2000, Lect. Notes Comput. Sci. 1893, 528-538 (2000)

Lozin, Vadim V.
Bipartite graphs without a skew star
Rutcor Research Report RRR 20-2001

Input:	A graph G in this class and an integer k.
Output:	True iff the cutwidth of G is at most k.

P. Heggernes, P. van 't Hof, D. Lokshtanov, J. Nederlof
Computing the cutwidth of bipartite permutation graphs in linear time
Proceedings of the 36th international conference on Graph-theoretic concepts in computer science WG 2010 75-87 (2010)

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)

M. Yannakakis
A polynomial algorithm for the min cut linear arrangement of trees
Journal of ACM Vol 32, 950-988 (1985)

Input:	A graph G in this class and an integer k.
Output:	True iff the treewidth of G is at most k.

H. Broersma, E. Dahlhaus, T. Kloks
A linear time algorithm for minimum fill--in and treewidth for distance--hereditary graphs
5th Twente workshop 1997

D. Meister
Treewidth and minimum fill-in on permutation graphs in linear time
Theoretical Comp. Sci. 411 No. 40-42 3685-3700 (2010)

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

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

H.L. Bodlaender
A linear time algorithm for finding tree-decompositions of small treewidth
SIAM J. Comput. 25 No.6 1305-1317 (1996)

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

H.L. Bodlaender
A linear time algorithm for finding tree-decompositions of small treewidth
SIAM J. Comput. 25 No.6 1305-1317 (1996)

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

H.L. Bodlaender
A linear time algorithm for finding tree-decompositions of small treewidth
SIAM J. Comput. 25 No.6 1305-1317 (1996)

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

H.L. Bodlaender
A linear time algorithm for finding tree-decompositions of small treewidth
SIAM J. Comput. 25 No.6 1305-1317 (1996)

H.J. Broersma, E. Dahlhaus, T. Kloks
Algorithms for the treewidth and minimum fill-in of HHD-free graphs
23rd Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. WG'97, Lecture Notes in Comp. Sci. 1335 (1997) 109-117

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

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

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

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

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

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

T. Kloks, D. Kratsch, J. Spinrad
On treewidth and minimum fill--in of asteroidal triple--free graphs
Theor. Comp. Sci. 175 1997 309--335

R. Garbe
Tree-width and path-width of comparability graphs of interval orders
20th Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. WG'94, Lecture Notes in Comp. Sci. 903 (1995) 26-37

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

T. Kloks, D. Kratsch, J. Spinrad
On treewidth and minimum fill--in of asteroidal triple--free graphs
Theor. Comp. Sci. 175 1997 309--335

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

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

L. Babel
Triangulating graphs with few P4's
Disc. Appl. Math. 89 45-57 (1998)

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

H.L. Bodlaender, T. Kloks, D. Kratsch, H. Mueller
Treewidth and minimum fill-in on d-trapezoid graphs
J. Graph Algorithms Appl. 2 1-23 (1998)

E. Dahlhaus
Minimum fill-in and treewidth on graphs modularly decomposable into chordal graphs
24th Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. WG'98, Lecture Notes in Comp. Sci. 1517 (1998) 351-358

V. Bouchitte, I. Todinca
Treewidth and minimum fill-in of weakly triangulated graphs
Annual symposium on theoretical aspects of computer science STACS 99, Lecture Notes in Comp. Sci. 1563 (1999) 197-206

Input:	A graph G in this class.
Output:	True iff each vertex of G can be assigned one colour out of 3 such that whenever two vertices are adjacent, they have different colours.

A. Leitert
3-Colourability of dually chordal graphs in linear time
Manuscript, 2012

H. Broersma, P.A. Golovach, D. Paulusma, J. Song
Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
Manuscript (2010)

J. Stacho
3-colouring of AT-free graphs in polynomial time
21st International Symposium on Algorithms and Computation ISAAC, Lecture Notes in Comp. Sci. LNCS 6507 144-155 (2010)

H. Broersma, P.A. Golovach, D. Paulusma, J. Song
Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
Manuscript (2010)

B. Randerath, I. Schiermeyer, M. Tewes
Three-colourability and forbidden subgraphs II: polynomial algorithms
Discrete Math. 251 137-212 (2002)

C.T. Hoang, M. Kaminski, V. Lozin, J. Sawada, X. Shu
Deciding k-colorability of P_5-free graphs in polynomial time
Algorithmica Vol.57 No.1 74-81 (2010)

B. Randerath, I. Schiermeyer
3-colorability in P for P_6-free graphs
Discrete Appl. Math. 136 299-313 (2004)

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)

H. Broersma, P.A. Golovach, D. Paulusma, J. Song
Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
Manuscript (2010)

H. Broersma, P.A. Golovach, D. Paulusma, J. Song
Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
Manuscript (2010)

K. Dabrowski, V. Lozin, R. Raman, B. Ries
Colouring vertices of triangle-free graphs
Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2010, LNCS 6410, 184-195 (2010)

H. Broersma, P.A. Golovach, D. Paulusma, J. Song
Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
Manuscript (2010)

(no preview available)

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of pairwise adjacent vertices, with |S| >= k.

V. Chv\'atal, C.T. Ho\`ang, N.V.R. Mahadev, D. de Werra
Four classes of perfectly orderable graphs
J. Graph Theory 11 1987 481--495

V. Chv\'atal, C.T. Ho\`ang, N.V.R. Mahadev, D. de Werra
Four classes of perfectly orderable graphs
J. Graph Theory 11 1987 481--495

M.C. Francis, D. Goncalves, P. Ochem
The maximum clique problem in multiple interval graphs
Proceedings of WG 2012, Lecture Notes in Computer Science 7551, 57-68 (2012)

F. Koenig
Sorting with objectives
Ph.D. thesis, Technische Universitaet Berlin (2009)

C.T. Hoang, F. Maffray, M. Mechebbek
A characterization of b-perfect graphs
Manuscript, 2010

Eschen, Elaine M.; Hoàng, Chính T.; Petrick, Mark D.T.; Sritharan, R
Disjoint clique cutsets in graphs without long holes
J. Graph Theory 48, No.4, 277-298 (2005)

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

A. Tiskin
Fast distance multiplication of unit-Monge matrices
Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms SODA 1287-1296 (2010)

A. Pecher, A.K. Wagler
Clique and chromatic number of circular-perfect graphs
Proceedings of ISCO 2010 - International Symposium on Combinatorial Optimization, Elec. Notes in Discrete Math 36 199-206 (2010)

Input:	A graph G in this class and an integer k.
Output:	True iff the vertices of G can be partitioned into k sets Si, such that whenever two vertices are in the same set Si, they are adjacent.

Hsu, Wen-Lian; Tsai, Kuo-Hui
Linear time algorithms on circular-arc graphs.
Inf. Process. Lett. 40, No.3, 123-129 (1991)

(no preview available)

E.M. Eschen, X. Wang
Algorithms for unipolar and generalized split graphs
Discrete Applied Math. 162 195-201 (2014)

Input:	A graph G in this class and an integer k.
Output:	True iff each vertex of G can be assigned one colour out of k such that whenever two vertices are adjacent, they have different colours.

V. Chv\'atal, C.T. Ho\`ang, N.V.R. Mahadev, D. de Werra
Four classes of perfectly orderable graphs
J. Graph Theory 11 1987 481--495

V. Chv\'atal, C.T. Ho\`ang, N.V.R. Mahadev, D. de Werra
Four classes of perfectly orderable graphs
J. Graph Theory 11 1987 481--495

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

H. Broersma, P.A. Golovach, D. Paulusma, J. Song
Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
Manuscript (2010)

K. Dabrowski, V. Lozin, R. Raman, B. Ries
Colouring vertices of triangle-free graphs
Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2010, LNCS 6410, 184-195 (2010)

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

K. Dabrowski, V. Lozin, R. Raman, B. Ries
Colouring vertices of triangle-free graphs
Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2010, LNCS 6410, 184-195 (2010)

K. Dabrowski, V. Lozin, R. Raman, B. Ries
Colouring vertices of triangle-free graphs
Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2010, LNCS 6410, 184-195 (2010)

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)

K. Dabrowski, V. Lozin, R. Raman, B. Ries
Colouring vertices of triangle-free graphs
Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2010, LNCS 6410, 184-195 (2010)

K. Dabrowski, V. Lozin, R. Raman, B. Ries
Colouring vertices of triangle-free graphs
Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2010, LNCS 6410, 184-195 (2010)

S.E. Markosjan, G.S. Gasparian, B. Reed
$\beta$--perfect graphs
J. Comb. Theory (B) 67 1996 1--11

C.T. Hoang, F. Maffray, M. Mechebbek
A characterization of b-perfect graphs
Manuscript, 2010

Eschen, Elaine M.; Hoàng, Chính T.; Petrick, Mark D.T.; Sritharan, R
Disjoint clique cutsets in graphs without long holes
J. Graph Theory 48, No.4, 277-298 (2005)

C.T. Hoang
Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
Discrete Appl. Math. 55 133-143 (1994)

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

A. Pecher, A.K. Wagler
Clique and chromatic number of circular-perfect graphs
Proceedings of ISCO 2010 - International Symposium on Combinatorial Optimization, Elec. Notes in Discrete Math 36 199-206 (2010)

C.T. Hoang
Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
Discrete Appl. Math. 55 133-143 (1994)

M.C. Golumbic
The complexity of comparability graph recognition and coloring
Computing 18 1977 199--208

K. Dabrowski, V. Lozin, R. Raman, B. Ries
Colouring vertices of triangle-free graphs
Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2010, LNCS 6410, 184-195 (2010)

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)

C.T. Hoang
Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
Discrete Appl. Math. 55 133-143 (1994)

G.B. Mertzios
An intersection model for multitolerance graphs: Efficient algorithms and hierarchy
Proc. of 21 annual ACM-SIAM symposium on Discrete algorithms SODA2011 1306-1317 (2011)

M. Gr\"otschel, L. Lov\'asz, A. Schrijver
The ellipsoid method and its consequences in combinatorial optimization
Combinatorica 1 169--197, 1981 Corrigendum

A. Brandstaedt, D. Kratsch
On the restriction of some NP-complete graph problems to permutation graphs.
Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 53-62 (1985)

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

R.B. Hayward, C. Ho\`ang, F. Maffray
Optimizing weakly triangulated graphs
Graphs and Combinatorics 5 339--349, Erratum: 6 (1990) 33--35 1989

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.

M.S. Chang
Efficient algorithms for the domination problems on interval and circular-arc graphs.
SIAM J. Comput. 27, No.6, 1671-1694 (1998)

Hsu, Wen-Lian; Tsai, Kuo-Hui
Linear time algorithms on circular-arc graphs.
Inf. Process. Lett. 40, No.3, 123-129 (1991)

F. Nicolai, T. Szymczak
Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs
Networks 37,No.3 117-128 (2001)

A. Brandst\"adt, V.D. Chepoi, F.F. Dragan
The algorithmic use of hypertree structure and maximum neighbourhood orderings
Discrete Appl. Math. 82 43--77 1998

F.F. Dragan, C.F. Prisacaru, V.D. Chepoi
Location problems in graphs and the Helly property (in Russian) (1987)
(appeared partially in Diskretnaja Matematika 4 67--73) 1992

M.S. Chang
Efficient algorithms for the domination problems on interval and circular-arc graphs.
SIAM J. Comput. 27, No.6, 1671-1694 (1998)

M. Farber, J.M. Keil
Domination in permutation graphs
J. Algorithms 6 (1985) 309-321

K. Tsai, W.L. Hsu
Fast algorithms for the dominating set problem on permutation graphs
Algorithmica 9 (1993) 601-614

C. Rhee, Y.D. Liang, S.K. Dhall, S. Lakshmivarahan
An O(n+m) algorithm for finding a minimum-weight dominating set in a permutation graph
SIAM J. Comput. 25 (1996) 404-419

A. Brandstaedt, D. Kratsch
On the restriction of some NP-complete graph problems to permutation graphs.
Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 53-62 (1985)

H.S. Chao, F.R. Hsu, R.C.T. Lee
An Optimal Algorithm for Finding the Minimum Cardinality Dominating Set on Permutation Graphs
Discrete Appl. Math. 102, No.3 159-173 (2000)

D. Rautenbach, V.E. Zverovich
Perfect graphs of strong domination and independent strong domination
Discrete Math. 226 No.1-3 297-311 (2001)

D. Kratsch
Domination and total domination in asteroidal triple-free graphs
Discrete Appl. Math. 99 No.1-3, 111-123 (2000)

I.E. Zverovich
The domination number of (K_p,P_5)-free graphs
Australas. J. Comb. 27 95-100 (2003)

I.E. Zverovich
The domination number of (K_p,P_5)-free graphs
Australas. J. Comb. 27 95-100 (2003)

T.W. Haynes, S.T. Hedetniemi, P.J. Slater (eds.)
Fundamentals of Domination in Graphs
Marcel Dekker, New York, Basel , Vol. 208 1998

T.W. Haynes, S.T. Hedetniemi, P.J. Slater (eds.)
Fundamentals of Domination in Graphs
Marcel Dekker, New York, Basel , Vol. 208 1998

J. Mark Keil, P. Belleville
Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs.
Discrete Appl. Math. 140, No.1-3, 73-89 (2004). [ISSN 0166-218X]

D. Kratsch, L. Stewart
Domination on cocomparability graphs
SIAM J. Discrete Math. 6(3) (1993) 400-417

H. Breu, D.G. Kirkpatrick
Algorithms for the dominating set and Steiner set problems in cocomparability graphs
Manuscript 1993

T.W. Haynes, S.T. Hedetniemi, P.J. Slater (eds.)
Fundamentals of Domination in Graphs
Marcel Dekker, New York, Basel , Vol. 208 1998

Damaschke, Peter; Müller, Haiko; Kratsch, Dieter
Domination in convex and chordal bipartite graphs.
Inf. Process. Lett. 36, No.5, 231-236 (1990)

T.W. Haynes, S.T. Hedetniemi, P.J. Slater (eds.)
Fundamentals of Domination in Graphs
Marcel Dekker, New York, Basel , Vol. 208 1998

E.S. Elmallah, L.K. Stewart
Independence and domination in polygon graphs
Discrete Appl. Math. 44 1993 65--77

A. Brandstaedt, D. Kratsch
On the restriction of some NP-complete graph problems to permutation graphs.
Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 53-62 (1985)

T. Kloks, C.-S. Liu, S.-L. Peng
Domination and independent domination on probe interval graphs
Proceedings of 23rd Workshop on Combinatorial Mathematics and Computation Theory 93-97 (2006)

M. Farber
Domination, independent domination, and duality in strongly chordal graphs.
Discrete Appl. Math. 7 1984 115--130

Liang, Y. Daniel
Dominations in trapezoid graphs.
Inf. Process. Lett. 52, No.6, 309-315 (1994)

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of vertices, with |S| <= k, such that every cycle in G contains a vertex from S.

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

Feedback vertex set on AT-free graphs
D. Kratsch, H. Mueller, I. Todinca
Discrete Appl. Math. 156 No. 10 1936-1947 (2008)

P. Festa, P.M. Pardalos, M.G.C. Resende
Feedback set problems
in: D.Z. Du, P.M. Pardalos, Handbook of Combinatorial Optimization, Supplement vol. A, Kluwer Academic Publishers, 209-259 (2000)

T. Kloks, C.-H. Liu, S.-H. Poon
Feedback vertex set on chordal bipartite graphs
Manuscript (2012)

J.P. Spinrad
Efficient graph representations
American Mathematical Society, Fields Institute Monograph Series 19 (2003)

S.R. Coorg, C.P. Rangan
Feedback vertex set on cocomparability graphs
Networks 26 101-111 (1995)

M.S Chang, Y.D. Liang
Minimum feedback vertex set in cocomparability graphs and convex bipartite graphs
Acta Informatica 34 337-346 (1997)

M.S Chang, Y.D. Liang
Minimum feedback vertex set in cocomparability graphs and convex bipartite graphs
Acta Informatica 34 337-346 (1997)

P. Festa, P.M. Pardalos, M.G.C. Resende
Feedback set problems
in: D.Z. Du, P.M. Pardalos, Handbook of Combinatorial Optimization, Supplement vol. A, Kluwer Academic Publishers, 209-259 (2000)

A. Brandstaedt, D. Kratsch
On the restriction of some NP-complete graph problems to permutation graphs.
Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 53-62 (1985)

A. Brandstaedt, D. Kratsch
On the restriction of some NP-complete graph problems to permutation graphs.
Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 53-62 (1985)

Y.D. Liang
On the feedback vertex set problem in permutation graphs
Information Proc. Lett. 52 123-129 (1994)

Y.D. Liang
On the feedback vertex set problem in permutation graphs
Information Proc. Lett. 52 123-129 (1994)

Input:	Graphs G and H in this class
Output:	True iff G and H are isomorphic.

A.R. Curtis, M.C. Lin, R.M. McConnell, Y. Nussbaum, F.J. Soulignac, J.P. Spinrad, J.L. Szwarcfiter
Isomorphism of graph classes related to the circular-ones property
DMTCS 15 No. 1 157-182 (2013)

K.S. Booth, G.S. Lueker
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms.
J. Comput. Syst. Sci. 13, 335-379 (1976). [ISSN 0022-0000]

C.J. Colbourn
On testing isomorphism of permutation graphs
Networks 11 1981 13--21

R.A. Wilson
Graphs, colourings and the four-colour theorem
Oxford University Press, London 2002

A.V. Aho, J.E. Hopcroft, J.D. Ullman
The design and analysis of computer algorithms
Addison--Wesley, Reading, Mass. 1974

D.G. Corneil, H. Lerchs, L. Stewart--Burlingham
Complement reducible graphs
Discrete Appl. Math. 3 1981 163--174

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)

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)

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)

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)

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Input:	A graph G in this class.
Output:	True iff G has a simple cycle that goes through every vertex of the graph.

D.G. Corneil, H. Lerchs, L. Stewart--Burlingham
Complement reducible graphs
Discrete Appl. Math. 3 1981 163--174

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

R.W. Hung, M.S. Chang
Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
Theoret. Comput. Sci. 341 411-440 (2005)

S.Y. Hsieh, C.W. Ho, T.S. Hsu, M.T. Ko
The Hamiltonian problem on distance-hereditary graphs
Discrete Appl. Math. 153 508-524 (2006)

J.M. Keil
Finding hamiltonian circuits in interval graphs
Information Proc. Lett. 20 201-206 (1985)

A. Brandstaedt, D. Kratsch
On the restriction of some NP-complete graph problems to permutation graphs.
Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 53-62 (1985)

W.K. Shih, T.C. Chen, W.L. Hsu
An O(n^2 log n) algorithm for the Hamiltonian cycle problem on circular-arc graphs
SIAM J. Comput. 21 No.6 1026-1046 (1992)

R.-W. Hung, M.-S. Chang, C.-H. Laio
The Hamiltonian cycle problem on circular-arc graphs
Proc. of the International MultiConference of Engineers and Computer Scientists IMECS 2009

Y. Daniel Liang, N. Blum
Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
Inform. Proc. Letters Vol.56 No.4 215-219 (1995)

J.S. Deogun, G. Steiner
Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
SIAM J. Computing 23 Issue 3 520-552 (1994)

Input:	A graph G in this class.
Output:	True iff G has a simple path that goes through every vertex of the graph.

D.G. Corneil, H. Lerchs, L. Stewart--Burlingham
Complement reducible graphs
Discrete Appl. Math. 3 1981 163--174

R.W. Hung, M.S. Chang
Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
Theoret. Comput. Sci. 341 411-440 (2005)

A. Brandstaedt, D. Kratsch
On the restriction of some NP-complete graph problems to permutation graphs.
Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 53-62 (1985)

G.B. Mertzios, I. Bezakova
Computing and counting longest paths on circular-arc graphs in polynomial time
Discrete Appl. Math, in press

J.S. Deogun, G. Steiner
Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
SIAM J. Computing 23 Issue 3 520-552 (1994)

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of pairwise non-adjacent vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.

M. Farber
Independent domination in chordal graphs
Operations Research Lett. 1 No.4 134-138 (1982)

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of pairwise non-adjacent vertices, such that |S| >= k.

V. Giakoumakis, F. Roussel, H. Thuillier
On $P_4$--tidy graphs
Discrete Math. and Theor. Comp. Sci. 1 1997 17--41

F. Gavril
The intersection graphs of subtrees in trees are exactly the chordal graphs
J. Comb. Theory (B) 16 1974 47--56

D.J. Rose, R.E. Tarjan, G.S. Lueker
Algorithmic aspects of vertex elimination on graph
SIAM J. Computing 5 1976 266--283

M.C. Golumbic, P.L Hammer
Stability in circular arc graphs.
J. Algorithms 9 (1988) 56-63

W.L. Hsu, J.P. Spinrad
Independent sets in circular arc graphs
J. Algorithms 19 (1995) 145-160

Hsu, Wen-Lian; Tsai, Kuo-Hui
Linear time algorithms on circular-arc graphs.
Inf. Process. Lett. 40, No.3, 123-129 (1991)

C.T. Ho\`ang
Recognition and optimization algorithms for co--triangulated graphs
Forschungsinstitut f\"ur Diskrete Mathematik, Bonn, 1990 Tech. Report No. 90637-OR

R.M. McConnell, J.P. Spinrad
Modular decomposition and transitive orientation
Discrete Math. 201 (1999) 189-241

V. Giakoumakis
$P_4$--laden graphs: a new class of brittle graphs
Inf. Proc. Letters 60 1996 29--36

F. Roussel, I. Rusu, H. Thuillier
On graphs with limited number of P_4-partners.
International Journal of Foundations of Computer Science, 1o 103-121 (1999)

V.E. Alekseev, V.V. Lozin
Augmenting graphs for independent sets
Discrete Appl. Math. 145, No.1 3-10 (2004)

R. Mosca
Independent sets in certain P_6-free graphs
Discrete Applied Math. 92 177-191 (1999)

M.U. Gerber, V.V. Lozin
On the stable set problem in special P_5-free graphs.
Rutcor Research Report 24-2000

N.V.R. Mahadev, B.A. Reed
A note on vertex orders for stability number
J. Graph Theory 30 113-120 (1999)

M.U. Gerber, V.V. Lozin
Robust algorithms for the stable set problem
Graphs and Combin., to appear

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)

R.E. Tarjan
Decomposition by clique separators
Discrete Math. 55 1985 221--232

(no preview available)

S.H. Whitesides
A method for solving certain graph recognition and optimization problems, with applications to perfect graphs
Annals of Discrete Math. 21 1984 281--297

N.V.R. Mahadev, B.A. Reed
A note on vertex orders for stability number
J. Graph Theory 30 113-120 (1999)

A. Hertz
Polynomially solvable cases for the maximum stable set problem
Discrete Appl. Math. 60 1995 195--210

N.V.R. Mahadev
Vertex deletion and stability number
Research report ORWP 90/2 Dept. of Mathematics, Swiss Fed.Inst. of Technology 1990

N.V.R. Mahadev, B.A. Reed
A note on vertex orders for stability number
J. Graph Theory 30 113-120 (1999)

A. Brandstaedt, V.V. Lozin
A note on \alpha-redundant vertices in graphs.
Discrete Appl. Math. 108 (2001) 301-308

M.U. Gerber, A. Hertz, D. Schindl
P_5-free graphs and the maximum stable set problem
Discrete Appl. Math. 132 109-119 (2004)

V. Alekseev, P. Lozin, R. Mosca
Maximum independent set problem and P_5-free graphs
Manuscript 2004

M. Burlet, J. Fonlupt
Polynomial algorithm to recognize a Meyniel graph
Annals of Discrete Math. 21 1984 225--252

A. Brandstaedt, V.V. Lozin
A note on \alpha-redundant vertices in graphs.
Discrete Appl. Math. 108 (2001) 301-308

V.E. Alekseev, V.V. Lozin
Augmenting graphs for independent sets
Discrete Appl. Math. 145, No.1 3-10 (2004)

M.U. Gerber, A. Hertz, V.V. Lozin
Stable sets in two subclasses of banner-free graphs
Discrete Appl. Math. 132 121-136 (2004)

M.U. Gerber, V.V. Lozin
Robust algorithms for the stable set problem
Graphs and Combin., to appear

V.L. Lozin, M. Milanic
On finding augmenting graphs
Rutcor Research Report 28-2005

V.E. Alekseev
On easy and hard hereditary classes of graphs with respect to the independent set problem
Discrete Appl. Math. 132, No.1-3 17-26 (2003)

N. Nash, D. Gregg
An output sensitive algorithm for computing a maximum independent set of a circle graph
Inform. Process. Lett. 110 No.16 630-634 (2010)

S.H. Whitesides
A method for solving certain graph recognition and optimization problems, with applications to perfect graphs
Annals of Discrete Math. 21 1984 281--297

Eschen, Elaine M.; Hoàng, Chính T.; Petrick, Mark D.T.; Sritharan, R
Disjoint clique cutsets in graphs without long holes
J. Graph Theory 48, No.4, 277-298 (2005)

E. Prisner
Hereditary clique-helly graphs
J. Comb. Math. Comb. Comput 14 216-220 (1993)

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

E.M. Eschen, X. Wang
Algorithms for unipolar and generalized split graphs
Discrete Applied Math. 162 195-201 (2014)

R. Hayward, J. Spinrad. R. Sritharan
Weakly chordal graph algorithms via handles
Proc. of the 11th symposium on Discrete Algorithms 42-49, 2000

R.B. Hayward, C. Ho\`ang, F. Maffray
Optimizing weakly triangulated graphs
Graphs and Combinatorics 5 339--349, Erratum: 6 (1990) 33--35 1989

(decision variant)

Input:	A graph G in this class and an integer k.
Output:	True iff the vertices of G can be partitioned into two sets A,B such that there are at least k edges in G with one endpoint in A and the other endpoint in B.

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

R. Crowston, M. Jones, M. Mnich
Max-cut parametrized above the Edwards-Erdős bound
Algorithmica Jan. 2014 1-24 (2014)

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)

H.L. Bodlaender, C.M.H. de Figueiredo, M. Gutierrez, T. Kloks, R. Niedermeier
Simple max-cut for split-indifference graphs and graphs with few P4s
Proceedings of 3rd Workshop on experimental and efficient algorithms WEA-04, LNCS 3059 87-99 (2004)

Input:	A graph G in this class.
Output:	True iff G is monopolar.

T. Ekim, P. Hell, J. Stacho, D. de Werra
Polarity of chordal graphs
Discrete Applied Mathematics 156 No. 13 2469-2479 (2008)

(no preview available)

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)

T. Ekim, P. Heggernes, D. Meister
Polar permutation graphs are polynomial-time recognisable
European J. Combin. 34 No.3 576-592 (2013)

Input:	A graph G in this class.
Output:	True iff G is polar.

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

T. Ekim, P. Hell, J. Stacho, D. de Werra
Polarity of chordal graphs
Discrete Applied Mathematics 156 No. 13 2469-2479 (2008)

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

T. Ekim, P. Heggernes, D. Meister
Polar permutation graphs are polynomial-time recognisable
European J. Combin. 34 No.3 576-592 (2013)

Input:	A graph G.
Output:	True iff G is in this graph class.

Input:	A graph G in this class with weight function on the vertices and a real k.
Output:	True iff G contains a set S of pairwise adjacent vertices, such that the sum of the weights of the vertices in S is at least k.

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

M.V. da Silva, K. Vuskovic
Triangulated neighborhoods in even-hole-free graphs
Discrete Math. 307 1065-1073 (2007)

M.M. Halldorson, S. Kitaev, A. Pyatkin
Alternation graphs
Proceedings of WG 2011, Lecture Notes in Computer Science 6986, 191-202 (2011)

W.-L. Hsu
Maximum weight clique algorithms for circular-arc graphs and circle graphs
SIAM J. Computing 14 No.1 224-231 (1985)

W.-L. Hsu
Maximum weight clique algorithms for circular-arc graphs and circle graphs
SIAM J. Computing 14 No.1 224-231 (1985)

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

F. Gavril
Maximum weight independent sets and cliques in intersection graphs of filaments.
Information Processing Letters 73(5-6) 181-188 (2000)

M. Kaufmann, J. Kratochvil, K.A. Lehmann, A.R. Subramanian
Max-tolerance graphs as intersection graphs: cliques, cycles and recognition
Proc. of 17th annual ACM-SIAM symposium on Discrete algorithms SODA'06 832-841 (2006)

(no preview available)

M. Barbato, D. Bezzi
Monopolar graphs: Complexity of computing classical graph parameters
Discrete Appl. Math. 291 277-285 (2021)

F. Maffray, M. Preissmann
Split--neighbourhood graphs and the strong perfect graph conjecture
J. Comb. Theory (B) 63 1995 294--309

Input:	A graph G in this class with weight function on the vertices and a real k.
Output:	True iff G contains a set S of vertices, such that the sum of the weights of the vertices in S is at most k and every cycle in G contains a vertex from S.

C.L. Lu, C.Y. Tang
A linear-time algorithm for the weighted feedback vertex problem on interval graphs
Information Proc. Lett. 61 107-111 (1997)

F. Gavril
Minimum weight feedback vertex sets in circle graphs
Information Proc. Lett. 107 No.1 1-6 (2008)

Input:	A graph G in this class with weight function on the vertices and a real k.
Output:	True iff G contains a set S of pairwise non-adjacent vertices, with the sum of the weights of the vertices in S at most k, such that every vertex in G is either in S or adjacent to a vertex in S.

M. Farber
Domination, independent domination, and duality in strongly chordal graphs.
Discrete Appl. Math. 7 1984 115--130

Input:	A graph G in this class with weight function on the vertices and a real k.
Output:	True iff G contains a set S of pairwise non-adjacent vertices, such that the sum of the weights of the vertices in S is at least k.

H. Bodlaender, A. Brandstaedt, D. Kratsch, M. Rao, J. Spinrad
Linear time algorithms for some NP-complete problems on (P_5, gem)-free graphs.
Manuscript 2003

F. Maffray, G. Morel
On 3-colorable P5-free graphs
Les Cahiers Leibniz No. 191

A. Frank
Some polynomial algorithms for certain graphs and hypergraphs.
Proc. 5th Br. comb. Conf., Aberdeen 1975, Congr. Numer. XV, 211-226 (1976).

A. Brandstaedt, S. Mahfud
Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
Information Processing Letters 84 (2002) 251-259

V. Kamakoti, C. Pandu Rangan
Efficient Transitive Reduction on Permutation Graphs and its Applications.
CSI JL on Computer Science and Informatics, Vol. 23, No. 3, pp. 52 - 59 (1993)

M. Farber
On diameters and radii of bridged graphs.
Discrete Math. 73 (1989) 249-260

H. Broersma, T. Kloks, D. Kratsch, H. M\"uller
Independent sets in asteroidal triple-free graphs
SIAM J. Discrete Math. 12, No.2, 276-287 (1999)

C.M.H. de Figueiredo, F. Maffray
Optimizing bull-free perfect graphs
SIAM J. Discrete Math. Vol.18 No.2 226-240 (2004)

V.E. Alekseev
On the local restrictions effect on the complexity of finding the graph independence number
Combinatorial-algebraic methods in applied mathematics Gorkiy Univ. Press, Gorkiy (1983) 3-13 (in Russian)

A. Brandstaedt, C.T. Hoang
On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
Theoretical Comp. Sci. 389, No.1-2, 295-306 (2007)

V. Lozin, R. Mosca
Independent sets and extensions of 2K_2-free graphs
Discrete Appl. Math. 146 74-80 (2005)

N.V.R. Mahadev
Vertex deletion and stability number
Research report ORWP 90/2 Dept. of Mathematics, Swiss Fed.Inst. of Technology 1990

N.V.R. Mahadev
Vertex deletion and stability number
Research report ORWP 90/2 Dept. of Mathematics, Swiss Fed.Inst. of Technology 1990

R. Mosca
Polynomial algorithms for the maximum stable set problem on particular classes of P_5-free graphs
Information Processing Letters 61 (1997) 137-144

A. Hertz
On a graph transformation that preserves the stability number
Research report ORWP 97/11 Dept. of Math., Swiss Fed. Inst. of Tech. 1997. Or: Yugosl. J. Oper. Res. 10, No.1, 1-12 (2000). [ISSN 0354-0243]

A. Brandstaedt, C.T. Hoang
On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
Theoretical Comp. Sci. 389, No.1-2, 295-306 (2007)

R. Mosca
Stable sets of maximum weight in (P_7, banner)-free graphs
Discrete Math. 308 Issue 1 20-33 (2008)

V. Alekseev, P. Lozin, R. Mosca
Maximum independent set problem and P_5-free graphs
Manuscript 2004

A. Brandstaedt, R. Mosca
On the structure and stability number of P_5 and co-chair-free graphs.
To appear in Discrete Appl. Math.

R. Mosca
Polynomial algorithms for the maximum stable set problem on particular classes of P_5-free graphs
Information Processing Letters 61 (1997) 137-144

A. Brandstaedt, V.B. Le, H.N. de Ridder
Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes.
Universitaet Rostock, Fachbereich Informatik, Preprint CS-14-01

V. Giakoumakis, I. Rusu
Weighted parameters in (P_5,\overline{P_5})-free graphs
Discrete Appl. Math. 80 (1997) 255-261

D. Lokshantov, M. Vatshelle, Y. Villanger
Independent set in P5-free graphs in polynomial time
Accepted for publication

A. Grzesik, T. Klimosova, M. Pilipczuk
Polynomial-time Algorithm for Maximum Weight Independent Set on P6-free Graphs
ACM Transactions on Algorithms 18 No.1 1-57 (2022)

V.V. Lozin
Conic reduction of graphs for the stable set problem.
Discrete Math. 222 (2000) 199-211

A. Brandstaedt, V.B. Le, H.N. de Ridder
Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes.
Universitaet Rostock, Fachbereich Informatik, Preprint CS-14-01

A. Brandstaedt, C.T. Hoang, V.B. Le
Stability number of bull- and chair-free graphs revisited
to appear in Discrete Appl. Math.

C. De Simone, A. Sassano
Stability number of bull-- and chair--free graphs
Discrete Appl. Math. 41 1993 121--129

A. Apostolico, M.J. Atallah, S.E. Hambrusch
New clique and independent set algorithms for circle graphs.
Discrete Appl. Math 36 (1992) 1-24 Erratum: Discrete Appl. Math 41 (1993) 179-180

A. Brandstaedt, V. Giakoumakis
Maximum Weight Independent Sets in Hole- and Co-Chair-Free Graphs
Inform. Proc. Lett. 112 67-71 (2012)

V.E. Alekseev
A polynomial algorithm for finding maximum independent sets in fork-free graphs
Discrete Ann. Operation Res., Ser. 1 6 (1999) 3-19 (in Russian)

F. Gavril
Maximum weight independent sets and cliques in intersection graphs of filaments.
Information Processing Letters 73(5-6) 181-188 (2000)

G.B. Mertzios
An intersection model for multitolerance graphs: Efficient algorithms and hierarchy
Proc. of 21 annual ACM-SIAM symposium on Discrete algorithms SODA2011 1306-1317 (2011)

A. Brandstaedt, V.V. Lozin, R. Mosca
Independent sets of maximum weight in apple-free graphs
SIAM J. Discrete Math. Vol.24 No.1 239-254 (2010)

E. Balas, C.S.Yu
On graphs with polynomially solvable maximum weight clique problem
Networks 19 (1989) 247-253

V.E. Alekseev, V.V. Lozin
Independent sets of maximum weight in (p,q)-colorable graphs
Rutcor Research Report 12-2002

M. Burlet, J.P. Uhry
Parity graphs
Annals of Discrete Math. 21 1984 253--277

M. Gr\"otschel, L. Lov\'asz, A. Schrijver
The ellipsoid method and its consequences in combinatorial optimization
Combinatorica 1 169--197, 1981 Corrigendum

J.L. Fouquet, V. Giakoumakis
On semi--$P_4$--sparse graphs
Discrete Math. 165/166 1997 277--300

E. Cenek, L. Stewart
Maximum independent set and maximum clique algorithms for overlap graphs
Discrete Appl. Math. 131, No.1 77-91 (2003)

G.B. Mertzios, I. Sau, S. Zaks
A new intersection model and improved algorithms for tolerance graphs
SIAM J. on Discrete Math. 23(4) 1800-1813 (2009)

J.P. Spinrad, R. Sritharan
Algorithms for weakly triangulated graphs
Discrete Appl. Math. 59 1995 181--191

(decision variant)

Input:	A graph G in this class with weight function on the edges and a real k.
Output:	True iff the vertices of G can be partitioned into two sets A,B such that the sum of weights of the edges in G with one endpoint in A and the other endpoint in B is at least k.

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)