Parameter: minimum clique cover

Definition:

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.

Relations

Minimal/maximal is with respect to the contents of ISGCI. Only references for direct bounds are given. Where no reference is given, check equivalent parameters.

Minimal upper bounds for this parameter

This parameter is a minimal upper bound for

Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current parameter.

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.
FPT
FPT from FPT-Linear on maximum independent set
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.
Unknown to ISGCI
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.
Unknown to ISGCI
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.
Unknown to ISGCI
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.
XP
XP on minimum dominating set [by definition]
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.
XP
XP on maximum independent set
[1807]
B.M.P. Jansen, V. Raman, M. Vatshelle
Parameter ecology for feedback vertex set
Tsinghua science and technology 19 No.4 387-409 (2014)

Graph isomorphism
[?]
Input: Graphs G and H in this class
Output: True iff G and H are isomorphic.
Unknown to ISGCI
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.
FPT
FPT on maximum independent set
[1860]
F.V. Fomin, P.A. Golovach, D. Sagunov, K. Simonov
Hamiltonicity, Path Cover, and Independence Number: An FPT Perspective
Manuscript

XP on maximum independent set
[1859]
N. Jedličková, J. Kratochvil
Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number
Manuscript

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.
FPT
FPT on maximum independent set
[1860]
F.V. Fomin, P.A. Golovach, D. Sagunov, K. Simonov
Hamiltonicity, Path Cover, and Independence Number: An FPT Perspective
Manuscript

XP on maximum independent set
[1859]
N. Jedličková, J. Kratochvil
Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number
Manuscript

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.
XP
XP on maximum independent set [by definition]
Maximum cut
[?]
(decision variant)
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into two sets A,B such that there are at least k edges in G with one endpoint in A and the other endpoint in B.
Unknown to ISGCI
Monopolarity
[?]
Input: A graph G in this class.
Output: True iff G is monopolar.
XP
XP on maximum independent set
[1817]
(no preview available)

Polarity
[?]
Input: A graph G in this class.
Output: True iff G is polar.
Unknown to ISGCI
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.
Unknown to ISGCI
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.
XP
XP on maximum induced matching
[1807]
B.M.P. Jansen, V. Raman, M. Vatshelle
Parameter ecology for feedback vertex set
Tsinghua science and technology 19 No.4 387-409 (2014)

Weighted independent dominating 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, with the sum of the weights of the vertices in S at most k, such that every vertex in G is either in S or adjacent to a vertex in S.
XP
XP on maximum independent set
[1750]
(no preview available)

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.
XP
XP on maximum independent set [by definition]

Graph classes

Bounded

back to top

Unbounded

back to top

Open

back to top

Unknown to ISGCI

back to top

AltStyle によって変換されたページ (->オリジナル) /