Graphclass: almost CIS

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

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

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)

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

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

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

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)

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)

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)

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

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)

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)

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

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

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)

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. Gr\"otschel, L. Lov\'asz, A. Schrijver
The ellipsoid method and its consequences in combinatorial optimization
Combinatorica 1 169--197, 1981 Corrigendum

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

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)

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

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

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

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

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

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

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

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. Hell, J. Stacho, D. de Werra
Polarity of chordal graphs
Discrete Applied Mathematics 156 No. 13 2469-2479 (2008)

Y. Wu, W. Zang, C-Q Zhang
A characterization of almost CIS graphs
Rutcor Research Report RRR 01-2009

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

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

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

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

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

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

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)

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. 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. Gr\"otschel, L. Lov\'asz, A. Schrijver
The ellipsoid method and its consequences in combinatorial optimization
Combinatorica 1 169--197, 1981 Corrigendum

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

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