(2K_2,C_4,C_5,S_3,X_{159},X_{160},\co{H},co-rising sun,net)--free graphs

Graphclass: (2K₂,C₄,C₅,S₃,X₁₅₉,X₁₆₀,H,co-rising sun,net)-free

Equivalent classes

Only references for direct inclusions are given. Where no reference is given for an equivalent class, check other equivalent classes or use the Java application.

probe threshold ∩ split

Forbidden subgraphs

[+]Details

2K₂ C₄ C₅ S₃ X₁₅₉ $X_{159}$ X₁₆₀ $X_{160}$ H $\co{H}$ co-rising sun net

Inclusions

The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.

Map

[+]Details

$Inclusion map for (2K_2,C_4,C_5,S_3,X_{159},X_{160},\co{H},co-rising sun,net)--free$

Problems

3-Colourability

[?]

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.

Linear

[+]Details

Linear from Colourability
Polynomial from Cliquewidth expression
Polynomial from Colourability

Linear on dually chordal [1505]
Polynomial on P₅-free [1242] [1441]
Polynomial on nK₂-free, fixed n [1434] [1431]
Polynomial on circular arc [1438]
Polynomial on 2P₃-free [1431]
Polynomial on circle [1438]
Polynomial on P₂ ∪ P₄-free [1431]
Polynomial on nP₃-free, fixed n [1431]
Polynomial [O(V^4)] on AT-free [1439]
Polynomial on P₆-free [1243]

Clique

[?]

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.

Linear

[+]Details

Linear from Weighted clique
Polynomial from Independent set on the complement
Polynomial from Weighted clique

Linear on Welsh-Powell perfect [221]
Linear on Matula perfect [221]
Polynomial on circular perfect [1408]
Polynomial [O(V log^2 V)] on circle [1466]
Polynomial on B₀-VPG
Polynomial [O(V log V)] on tolerance
Polynomial [O(V log V)] on multitolerance
Polynomial [O(V log V)] on boxicity 2 [604]
Polynomial on 2-track [1553] [1554]
Polynomial on biclique separable [1304]
Polynomial on b-perfect [1478]

Clique cover

[?]

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

Linear

[+]Details

Polynomial from Cliquewidth expression
Polynomial from Colourability on the complement

Linear on circular arc [1158]
Polynomial [O(V log^{d-1} V)] on d-trapezoid
Polynomial [O(V log log V)] on trapezoid

Cliquewidth

[?]

Whether the cliquewidth of the graphs in this class is bounded by a constant k .
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,
connecting all vertices with label i to all vertices with label j.

Bounded

[+]Details

Bounded on probe distance-hereditary
Bounded on cliquewidth 4
Bounded on probe P₄-sparse
Bounded on probe P₄-reducible
Bounded on probe ptolemaic

Cliquewidth expression

[?]

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.

Polynomial

[+]Details

Polynomial from Cliquewidth

Colourability

[?]

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.

Linear

[+]Details

Polynomial from Cliquewidth expression

Linear on Welsh-Powell perfect [221]
Linear on Matula perfect [221]
Linear on chordal [453]
Polynomial [O(V^2)] on chordal [1424]
Polynomial [O(V log log V)] on trapezoid
Polynomial on biclique separable [1304]
Polynomial [O(VE)] on perfectly orderable [1424] [1382]
Polynomial on circular perfect [1408]
Polynomial [O(V log V)] on multitolerance [1497]
Polynomial [O(V log V)] on permutation [453]
Polynomial [O(V^3)] on co-comparability [451]
Polynomial [O(V log V)] on tolerance
Polynomial [O(V^4E)] on weakly chordal [530]
Polynomial [O(V^2)] on comparability [1424]
Polynomial on clique separable [1424]
Polynomial on perfect [476]
Polynomial on b-perfect [1478]
Polynomial on permutation [1165]
Polynomial on β-perfect [771]

Cutwidth

[?]

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

Unknown to ISGCI

[+]Details

Domination

[?]

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.

Linear

[+]Details

Polynomial from Cliquewidth expression

Linear on interval [1143]
Linear on circular arc [1143] [1158]
Linear [O(V)] on permutation [1342] [1147] [1148] [1149] [1165]
Linear on dually chordal [143] [332]
Polynomial on trapezoid [1155]
Polynomial on AT-free [1152]
Polynomial on k-polygon [352]
Polynomial on probe interval [1340]
Polynomial on strongly chordal [374]
Polynomial on co-comparability [1150] [1151]
Polynomial on permutation [1165]
Polynomial [O(n^2 log^5 n)] on co-bounded tolerance [1172]
Polynomial on co-interval ∪ interval
Polynomial on directed path [524]

Feedback vertex set

[?]

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.

Linear

[+]Details

Linear from Weighted feedback vertex set
Polynomial from Weighted feedback vertex set

Polynomial on chordal [1574]
Polynomial [O(VE)] on trapezoid [1576]
Polynomial [O(V^6)] on permutation [1165]
Polynomial [O(VE^2)] on permutation [1165]
Polynomial [O(V^4)] on co-comparability [1578]
Polynomial [O(VE)] on permutation [1576]
Polynomial on circular arc [995]
Polynomial [O(V^8E^2)] on AT-free [1581]
Polynomial on interval [1574]
Polynomial [O(V^2E)] on co-comparability [1579]

Hamiltonian cycle

[?]

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

Linear

[+]Details

Polynomial from Cliquewidth expression

Linear on interval [1529]
Polynomial [O(V \Delta(G))] on circular arc [1536]
Polynomial on co-comparability [1524]
Polynomial [O(V^2 log V)] on circular arc [1527]
Polynomial [O(V log V)] on interval

Hamiltonian path

[?]

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

Polynomial

[+]Details

Polynomial from Cliquewidth expression

Polynomial [O(V^4)] on circular arc [1543]
Polynomial [O(V log V)] on interval
Polynomial on co-comparability [1524]

Independent set

[?]

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.

Linear

[+]Details

Linear from Weighted independent set
Polynomial from Clique on the complement
Polynomial from Weighted independent set

Linear on extended P₄-laden [438]
Linear on chordal [425] [931]
Linear on co-comparability [1100]
Linear on co-chordal [558]
Linear [O(n)] on circular arc [1105] [1106] [1158]
Polynomial on (C₄,P₆)-free [1351] [1352]
Polynomial on co-hereditary clique-Helly [1298]
Polynomial on (P₅,P₂ ∪ P₃)-free [1350]
Polynomial on clique separable [1081]
Polynomial on (C₅,P₅,P₂ ∪ P₃)-free [1118]
Polynomial on (P,P₈)-free [1306]
Polynomial on EPT [1019] [1381]
Polynomial [O(V^8)] on (P,P₇)-free [1351]
Polynomial [O(V^{5})] on (K_3,3-e,P₅,X₉₉)-free [1307]
Polynomial on (K_2,3,P,P₅)-free [1346] [1107]
Polynomial on Gallai [1081]
Polynomial on (C₆,K_3,3+e,P,P₇,X₃₇,X₄₁)-free [1346]
Polynomial [O(V min(d,\alpha))] on circle [1465]
Polynomial [O(VE)] on (P,P₅)-free [1117]
Polynomial on (P,star_1,2,5)-free [1349]
Polynomial on (K_3,3-e,P₅)-free [1246]
Polynomial [O(nm)] on (K_3,3-e,P₅,X₉₈)-free [1117]
Polynomial [O(VE)] on weakly chordal [530] [1119]
Polynomial on (E,P)-free [1305]
Polynomial on Meyniel [169]
Polynomial on (P,T₂)-free [1305]
Polynomial on comparability [453]
Polynomial on co-biclique separable [1304]

Recognition

[?]

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

Linear

[+]Details

Linear on probe threshold ∩ split
Polynomial

Finite forbidden subgraph characterization

Treewidth

[?]

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

Linear

[+]Details

Linear on permutation [1418]
Polynomial on co-comparability graphs of dimension d posets [675]
Polynomial on split [119]
Polynomial on interval [119]
Polynomial on circle [119]
Polynomial on d-trapezoid [675]
Polynomial on co-chordal [119]
Polynomial on co-interval [1416]
Polynomial on chordal [119]
Polynomial on d-trapezoid
Polynomial [O((V+E) log V)] on weak bipolarizable [1419]
Polynomial on HHD-free [1420]
Polynomial on permutation [119]
Polynomial [O(V^2)] on trapezoid [1417]
Polynomial on circular arc [119]
Polynomial on circular permutation [119]
Polynomial on weakly chordal [1421]

Weighted clique

[?]

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.

Linear

[+]Details

Polynomial from Weighted independent set on the complement
Polynomial from Cliquewidth expression

Linear on comparability [453]
Polynomial on co-comparability ∪ comparability
Polynomial [O(V^2 + E log log V)] on circle [1429]
Polynomial [O(V^2 log V)] on circle-trapezoid
Polynomial on alternation [1598]
Polynomial on max-tolerance [1481]
Polynomial [O(VE)] on circular arc [453] [1429]
Polynomial [O(V log log V)] on trapezoid
Polynomial on interval filament [1159]
Polynomial [O(VE)] on perfectly orderable [1424]

Weighted feedback vertex set

[?]

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.

Linear

[+]Details

Polynomial from Cliquewidth expression

Linear on interval [1577]
Polynomial on circle [1585]
Polynomial [O(V^{2n+5})] on circle-n-gon, fixed n

Weighted independent set

[?]

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.

Linear

[+]Details

Polynomial from Weighted clique on the complement
Polynomial from Cliquewidth expression

Linear on (2K₂,C₄)-free
Linear on permutation [1164]
Linear on chordal [1166]
Polynomial [O(V^9 E)] on (P,P₇)-free [1452]
Polynomial [O(V log log V)] on trapezoid
Polynomial [O(n^4)] on (C₄,P₅)-free
Polynomial on (n+4)-pan-free [1447]
Polynomial [O(n^6)] on (K_3,3,P₅)-free
Polynomial [O(V^4)] on weakly chordal [997]
Polynomial on nK₂-free, fixed n [1102]
Polynomial on (K_2,3,P₅)-free [1110]
Polynomial on 2K₂-free [1160]
Polynomial on subtree overlap [1123]
Polynomial on interval filament [1159]
Polynomial on (C₄,C₅,T₂)-free [1108]
Polynomial on (K_2,3,P,hole)-free [1107]
Polynomial on (K_2,3,P,P₅)-free [1107]
Polynomial on perfect [476]
Polynomial [O(n^8)] on (K_4,4,P₅)-free
Polynomial [O(V^2 log log V)] on circular trapezoid
Polynomial [O(E + V log V)] on multitolerance [1497]
Polynomial on (P₅,house)-free [1109]
Polynomial [O(V log^{d-1} V)] on d-trapezoid
Polynomial [O(V log V)] on tolerance
Polynomial [O(V^4)] on AT-free [160]
Polynomial on (P,P₅)-free [1353]
Polynomial on (P₅,X₈₂,X₈₃)-free [1246]
Polynomial on (C₄,P₆)-free [1353]
Polynomial [O(V^2)] on circle [1121]
Polynomial [O(V + V \Delta(G))] on 2-thin
Polynomial on K₂ ∪ claw-free [1290]
Polynomial [O(n^{6p+2})] on (p,q<=2)-colorable [1116]
Polynomial [O(V^2)] on tolerance [1498]
Polynomial [O(ln)] on circular arc
Polynomial [O(V^2)] on circle-trapezoid

Graphclass: (2K₂,C₄,C₅,S₃,X₁₅₉,X₁₆₀,H,co-rising sun,net)-free

Equivalent classes

Complement classes

Forbidden subgraphs

Inclusions

Map

Minimal superclasses

Maximal subclasses

Problems

Graphclass: (2K2,C4,C5,S3,X159,X160,H,co-rising sun,net)-free

Equivalent classes

Complement classes

Forbidden subgraphs

Inclusions

Map

Minimal superclasses

Maximal subclasses

Problems

Graphclass: (2K₂,C₄,C₅,S₃,X₁₅₉,X₁₆₀,H,co-rising sun,net)-free