Graphclass: (C_n+4 ∪ K₁,S₃ ∪ K₁,X₄₂,T₂,X₂,X₃,odd-cycle ∪ K₁,even anti-hole,net)-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)}$ )

(no preview available)

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

V.V. Lozin, C. Mayhill, V. Zamaraev
Locally bounded coverings and factorial properties of graphs
European J. Combin. 33 No.4 534-543 (2012)

(no preview available)

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

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

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

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 .

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.

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.

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

M. Kaminski, V. Lozin
Vertex 3-colorability of claw-free graphs
Algorithmic Operations Research Vol.2 15-21 (2007)

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)

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

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

B. Bhattacharya, P. Hell, J. Huang
A linear algorithm for maximum weight cliques in proper circular arc graphs
SIAM J. Discrete Math. 9 No. 2 274-289 (1996)

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)

A. Brandstaedt, F. Dragan
On linear and circular structure of (claw, net)-free graph
To appear in Discrete Appl. Math.

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

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)

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)

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)

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)

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

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)

D. Duffus, R.J. Gould, M.S. Jacobson
Forbidden subgraphs and the Hamiltonian theme.
The theory and applications of graphs, 4th int. Conf., Kalamazoo/Mich. 1980, 297-316 (1981).

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)

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

D. Duffus, R.J. Gould, M.S. Jacobson
Forbidden subgraphs and the Hamiltonian theme.
The theory and applications of graphs, 4th int. Conf., Kalamazoo/Mich. 1980, 297-316 (1981).

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)

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

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

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)

A. Brandstaedt, F. Dragan
On linear and circular structure of (claw, net)-free graph
To appear in Discrete Appl. Math.

P.L. Hammer, N.V.R. Mahadev, D. de Werra
The struction of a graph: application to CN--free graphs
Combinatorica 5 1985 141--147

N. Sbihi
Algorithme de recherche d'un stable de cardinalit\'e maximum dans un graphe sans \'etoile
Discrete Math. 29 1980 53--76

(decision variant)

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

R. Churchley, J. Huang
On the polarity and monopolarity of graphs
J. Graph Theory 76 No. 2 1138-148 (2014)

A.C. Tucker
Matrix characterizations of circular--arc graphs
Pacific J. Math. 39 1971 535--545

X. Deng, P. Hell, J. Huang
Linear time representation algorithms for proper circular arc graphs and proper interval graphs
SIAM J. Computing 25 1996 390--403

P. Hell, J. Bang--Jensen, J. Huang
Local tournaments and proper circular arc graphs
{\sl Intern. Symp. SIGAL},Lecture Notes in Comp. Sci. 450 1990 101--108

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)

B. Bhattacharya, P. Hell, J. Huang
A linear algorithm for maximum weight cliques in proper circular arc graphs
SIAM J. Discrete Math. 9 No. 2 274-289 (1996)

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)

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

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

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

G.J. Minty
On maximal independent sets of vertices in claw--free graphs
J. Comb. Theory (B) 28 1980 284--304

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)

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. Cenek, L. Stewart
Maximum independent set and maximum clique algorithms for overlap graphs
Discrete Appl. Math. 131, No.1 77-91 (2003)

(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)