clique cover number
tags: covering vertices
equivalent to: clique cover number
Relations
| Other | Relation from | Relation to |
|---|---|---|
| acyclic chromatic number | exclusion | exclusion |
| arboricity | exclusion | exclusion |
| average degree | exclusion | exclusion |
| average distance | exclusion | upper bound |
| bandwidth | exclusion | exclusion |
| bipartite | unbounded | exclusion |
| bipartite number | exclusion | upper bound |
| bisection bandwidth | exclusion | exclusion |
| block | unbounded | exclusion |
| book thickness | exclusion | exclusion |
| boolean width | exclusion | exclusion |
| bounded components | exclusion | exclusion |
| boxicity | exclusion | exclusion |
| branch width | exclusion | exclusion |
| c-closure | exclusion | exclusion |
| carving-width | exclusion | exclusion |
| chordal | unbounded | exclusion |
| chordality | exclusion | exclusion |
| chromatic number | exclusion | exclusion |
| clique-tree-width | exclusion | exclusion |
| clique-width | exclusion | exclusion |
| cluster | unbounded | exclusion |
| co-cluster | unbounded | exclusion |
| cograph | unbounded | exclusion |
| complete | constant | exclusion |
| connected | unbounded | unknown to HOPS |
| cutwidth | exclusion | exclusion |
| cycle | unbounded | exclusion |
| cycles | unbounded | exclusion |
| d-path-free | exclusion | exclusion |
| degeneracy | exclusion | exclusion |
| degree treewidth | exclusion | exclusion |
| diameter | exclusion | upper bound |
| diameter+max degree | exclusion | exclusion |
| disjoint cycles | unbounded | exclusion |
| distance to bipartite | exclusion | exclusion |
| distance to block | exclusion | exclusion |
| distance to bounded components | exclusion | exclusion |
| distance to chordal | exclusion | exclusion |
| distance to cluster | exclusion | exclusion |
| distance to co-cluster | exclusion | exclusion |
| distance to cograph | exclusion | exclusion |
| distance to complete | upper bound | exclusion |
| distance to edgeless | exclusion | exclusion |
| distance to forest | exclusion | exclusion |
| distance to interval | exclusion | exclusion |
| distance to linear forest | exclusion | exclusion |
| distance to maximum degree | exclusion | exclusion |
| distance to outerplanar | exclusion | exclusion |
| distance to perfect | exclusion | exclusion |
| distance to planar | exclusion | exclusion |
| distance to stars | exclusion | exclusion |
| domatic number | exclusion | exclusion |
| domination number | unknown to HOPS | upper bound |
| edge clique cover number | exclusion | exclusion |
| edge connectivity | exclusion | exclusion |
| edgeless | unbounded | exclusion |
| feedback edge set | exclusion | exclusion |
| feedback vertex set | exclusion | exclusion |
| forest | unbounded | exclusion |
| genus | exclusion | exclusion |
| girth | exclusion | upper bound |
| grid | unbounded | exclusion |
| h-index | exclusion | exclusion |
| inf-flip-width | exclusion | exclusion |
| interval | unbounded | exclusion |
| iterated type partitions | exclusion | exclusion |
| linear clique-width | exclusion | exclusion |
| linear forest | unbounded | exclusion |
| linear NLC-width | exclusion | exclusion |
| linear rank-width | exclusion | exclusion |
| maximum clique | exclusion | exclusion |
| maximum degree | exclusion | exclusion |
| maximum independent set | unknown to HOPS | upper bound |
| maximum induced matching | exclusion | upper bound |
| maximum leaf number | exclusion | exclusion |
| maximum matching | exclusion | exclusion |
| maximum matching on bipartite graphs | exclusion | exclusion |
| mim-width | exclusion | unknown to HOPS |
| minimum degree | exclusion | exclusion |
| mm-width | exclusion | exclusion |
| modular-width | exclusion | exclusion |
| module-width | exclusion | exclusion |
| neighborhood diversity | exclusion | exclusion |
| NLC-width | exclusion | exclusion |
| NLCT-width | exclusion | exclusion |
| odd cycle transversal | exclusion | exclusion |
| outerplanar | unbounded | exclusion |
| path | unbounded | exclusion |
| pathwidth | exclusion | exclusion |
| pathwidth+maxdegree | exclusion | exclusion |
| perfect | unbounded | exclusion |
| planar | unbounded | exclusion |
| radius-r flip-width | exclusion | unknown to HOPS |
| rank-width | exclusion | exclusion |
| shrub-depth | exclusion | exclusion |
| sim-width | exclusion | unknown to HOPS |
| star | unknown to HOPS | exclusion |
| stars | unbounded | exclusion |
| topological bandwidth | exclusion | exclusion |
| tree | unbounded | exclusion |
| tree-independence number | exclusion | unknown to HOPS |
| treedepth | exclusion | exclusion |
| treelength | exclusion | upper bound |
| treewidth | exclusion | exclusion |
| twin-cover number | exclusion | exclusion |
| twin-width | exclusion | exclusion |
| vertex connectivity | unknown to HOPS | exclusion |
| vertex cover | exclusion | exclusion |
| vertex integrity | exclusion | exclusion |
Results
- 2022 Expanding the Graph Parameter Hierarchy by Tran
- page 40 : bounded twin-width does not imply bounded clique cover number – Proposition 6.7. Twin-width is incomparable to Clique Cover Number.
- page 40 : bounded clique cover number does not imply bounded twin-width – Proposition 6.7. Twin-width is incomparable to Clique Cover Number.
- 2019 The Graph Parameter Hierarchy by Sorge
- page 11 : clique cover number upper bounds maximum independent set by a linear function – Lemma 4.26. The minimum clique cover number $c$ strictly upper bounds the independence number $\alpha$.
- Comparing Graph Parameters by Schröder
- page 15 : bounded clique cover number does not imply bounded distance to perfect – Proposition 3.6
- page 16 : bounded clique cover number does not imply bounded clique-width – Proposition 3.9
- page 19 : bounded clique cover number does not imply bounded chordality – Proposition 3.11
- https://en.wikipedia.org/wiki/Clique_cover
- clique cover number – … is a partition of the vertices into cliques … A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum $k$ for which a clique cover exists is called the clique cover number of the given graph.
- unknown source
- distance to complete upper bounds clique cover number by a linear function – We cover the $k$ vertices of the modulator by cliques of size $1$ and cover the remaining clique by another one.