threshold graphs

Graphclass: threshold

The following definitions are equivalent:

The following are equivalent definitions of the threshold dimension of a graph:
- Let G be a graph with nodes v₁...v_n. The characteristic vector x of X\subseteq V has x_i = 1 if v_i in X and 0 otherwise. The treshold dimension \theta(G) if the minimum number k of linear inequalities a_j1x₁ + ... + a_jnx_n <= t_j (1<=j<= k) such that X is an independent set iff its characteristic vector x satisfies this system of inequalities.
- The treshold dimension of a graph (V,E) is the minimum number k of threshold graphs (V,E_i) such that E equals the union of all E_i.
A graph is a threshold graph iff its threshold dimension is at most 1.
A graph is a threshold graph if there is a real number S (the threshold) and for every vertex v there is a real weight a_v such that: vw is an edge iff a_v + a_w >= S.
A graph is a threshold graph if it can constructed from the empty graph by repeatedly adding either an isolated vertex or a dominating vertex.

References

Complement classes

self-complementary

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.

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
Linear from Cliquewidth expression
Polynomial from Colourability
Polynomial from Cliquewidth expression

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

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 Weighted clique
Polynomial from Independent set on the complement

Linear on Welsh-Powell perfect [221]
Linear on Matula perfect [221]
Polynomial on circular perfect [1408]
Polynomial on b-perfect [1478]
Polynomial [O(V log^2 V)] on circle [1466]
Polynomial on biclique separable [1304]
Polynomial [O(V log V)] on boxicity 2 [604]

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 Colourability on the complement
Polynomial from Cliquewidth expression

Linear on circular arc [1158]

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 from Cliquewidth on the complement

Bounded on (6,2) [1175]
Bounded on tree-cograph
Bounded on probe P₄-sparse
Bounded on (bull,fork,gem)-free [1185]
Bounded on distance-hereditary [1177]
Bounded on (9,6) [488]
Bounded on (bull,fork,house)-free [1124] [1185]
Bounded on (q,q-4), fixed q [1175]
Bounded on (P₅,bull,house)-free [1187] [1185]
Bounded on (P,P,co-fork,fork)-free [1185]
Bounded on (7,3) [1175]
Bounded on (5,1) [1175]
Bounded on (co-gem,gem)-free [1188] [1185]
Bounded on semi-P₄-sparse [1186]
Bounded on (P₅,gem)-free [1189] [1171] [1185]
Bounded on (bull,co-fork,fork)-free [1124] [1185]
Bounded on cliquewidth 4
Bounded on cliquewidth 3
Bounded on cliquewidth 2
Bounded on probe distance-hereditary
Bounded on (q, q-3), fixed q>= 7 [1176]
Bounded on probe ptolemaic
Bounded on probe P₄-reducible
Bounded on (P,fork,house)-free [1185] [1186]
Bounded on (P,fork,gem)-free [1184] [1185]
Bounded on partner-limited [1179]
Bounded on (P₅,fork,house)-free [1185] [402]

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.

Linear

[+]Details

Polynomial from Cliquewidth
Polynomial from Cliquewidth expression on the complement

Linear on (P₅,fork,house)-free [1185] [402]
Linear on (5,1) [1175]
Linear on (bull,co-fork,fork)-free [1124] [1185]
Linear on (bull,fork,house)-free [1124] [1185]
Linear on (P₅,bull,house)-free [1187] [1185]
Linear on partner-limited [1179]
Linear on (P,fork,gem)-free [1184] [1185]
Linear on (q, q-3), fixed q>= 7 [1176]
Linear on (P,P,co-fork,fork)-free [1185]
Linear on (9,6) [488]
Linear on (P,fork,house)-free [1185] [1186]
Linear on (6,2) [1175]
Linear on distance-hereditary [1177]
Linear on (7,3) [1175]
Linear on semi-P₄-sparse [1186]
Linear on cliquewidth 2
Linear on (q,q-4), fixed q [1175]
Linear on P₄-tidy [1175]
Linear on P₄-tidy [1175]
Linear on (bull,fork,gem)-free [1185]
Polynomial [O(V^2E)] on cliquewidth 3 [1178]
Polynomial on tree-cograph

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
Polynomial from Clique cover on the complement

Linear on Matula perfect [221]
Linear on Welsh-Powell perfect [221]
Linear on chordal [453]
Polynomial on P₄-free [1433]
Polynomial [O(V^2)] on comparability [1424]
Polynomial [O(VE)] on perfectly orderable [1424] [1382]
Polynomial [O(V^4E)] on weakly chordal [530]
Polynomial [O(V log V)] on permutation [453]
Polynomial [O(V^2)] on chordal [1424]
Polynomial on b-perfect [1478]
Polynomial on perfect [476]
Polynomial on biclique separable [1304]
Polynomial on circular perfect [1408]
Polynomial on β-perfect [771]
Polynomial on clique separable [1424]

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

Linear from Cliquewidth expression
Polynomial from Cliquewidth expression

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

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 Weighted independent set
Polynomial from Clique on the complement

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

Recognition

[?]

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

Linear

[+]Details

Linear [218] [509]
Polynomial on (2K₂,C₄,P₄)-free

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]
Linear on distance-hereditary [159]
Polynomial on co-comparability graphs of dimension d posets [675]
Polynomial on co-chordal [119]
Polynomial on co-interval [1416]
Polynomial on (q,q-4), fixed q [1422]
Polynomial on circular arc [119]
Polynomial on d-trapezoid
Polynomial on circle [119]
Polynomial on interval [119]
Polynomial on chordal [119]
Polynomial on split [119]
Polynomial [O(V^2)] on trapezoid [1417]
Polynomial on weakly chordal [1421]
Polynomial [O((V+E) log V)] on weak bipolarizable [1419]
Polynomial on circular permutation [119]
Polynomial on HHD-free [1420]
Polynomial on cograph [119]
Polynomial on permutation [119]
Polynomial on d-trapezoid [675]

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

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

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

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

Linear from Cliquewidth expression
Polynomial from Weighted clique on the complement
Polynomial from Cliquewidth expression

Linear on (P₅,gem)-free [1170]
Linear on chordal [1166]
Linear on permutation [1164]
Linear on distance-hereditary
Linear on (2K₂,C₄)-free
Polynomial on (C₄,C₅,T₂)-free [1108]
Polynomial [O(VE)] on co-gem-free
Polynomial [O(n^4)] on (C₄,P₅)-free
Polynomial on (P,P₅,3K₂,gem)-free [1114]
Polynomial [O(V^2)] on circle [1121]
Polynomial on fork-free [1099]
Polynomial on semi-P₄-sparse [402]
Polynomial [O(V^4)] on weakly chordal [997]
Polynomial on (P,P₅)-free [1353]
Polynomial on parity [170]
Polynomial on interval filament [1159]
Polynomial on 2K₂-free [1160]
Polynomial [O(n^6)] on (K_3,3,P₅)-free
Polynomial [O(V^4)] on AT-free [160]
Polynomial on K₂ ∪ claw-free [1290]
Polynomial [O(n^{6p+2})] on (p,q<=2)-colorable [1116]
Polynomial [O(ln)] on circular arc
Polynomial on perfect [476]
Polynomial on (P,butterfly,fork,gem)-free [1104]
Polynomial on (K_2,3,P,hole)-free [1107]
Polynomial on (K_2,3,P₅)-free [1110]
Polynomial [O(VE)] on (bull,fork)-free [1124] [307]
Polynomial [O(V + V \Delta(G))] on 2-thin
Polynomial on (P₅,house)-free [1109]
Polynomial on subtree overlap [1123]
Polynomial on (C₄,P₆)-free [1353]
Polynomial on (K_2,3,P,P₅)-free [1107]
Polynomial on (n+4)-pan-free [1447]
Polynomial on (P₅,co-fork)-free [1161]
Polynomial [O(VE)] on (P,fork)-free [1125]
Polynomial [O(V^5E^3)] on Berge ∩ bull-free [1278]
Polynomial [O(n logn logn)] on trapezoid
Polynomial [O(V^9 E)] on (P,P₇)-free [1452]
Polynomial on (P₅,X₈₂,X₈₃)-free [1246]
Polynomial [O(VE)] on (P₅,fork)-free [1125]
Polynomial [O(n^8)] on (K_4,4,P₅)-free
Polynomial on nK₂-free, fixed n [1102]
Polynomial on (co-fork,hole)-free [1494]

Graphclass: threshold

References

Equivalent classes

Complement classes

Inclusions

Map

Minimal superclasses

Problems

Graphclass: threshold

References

Equivalent classes

Complement classes

Related classes

Inclusions

Map

Minimal superclasses

Problems