Graphclass: bipartite ∩ tolerance

Definition:

A collection of sets U is consecutively orderable if the sets can be indexed U1 ,..,Un , such that for all i <= j <= k, whenever x is in Ui and in Uk , then x is in Uj .
A bipartite graph G=(V,E) is in bipartite ∩ tolerance if there exist a consecutively orderable partition of E into star s.

References

[1485] [1486]

Equivalent classes

[+]Details

Related classes

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

Minimal superclasses

[+]Details

Maximal subclasses

[+]Details

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
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
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 Si, such that whenever two vertices are in the same set Si, they are adjacent.
Polynomial [+]Details
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.
Unbounded [+]Details
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.
Unbounded or NP-complete [+]Details
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
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.
Unknown to ISGCI [+]Details
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.
Polynomial [+]Details
Recognition
[?]
Input: A graph G.
Output: True iff G is in this graph class.
Linear [+]Details
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).
Polynomial [+]Details
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
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.
Polynomial [+]Details