tree-independence number
tags: tree decomposition
equivalent to: tree-independence number
Relations
| Other | Relation from | Relation to |
|---|---|---|
| acyclic chromatic number | unknown to HOPS | unknown to HOPS |
| arboricity | unknown to HOPS | unknown to HOPS |
| average degree | unknown to HOPS | unknown to HOPS |
| average distance | unknown to HOPS | exclusion |
| bandwidth | upper bound | exclusion |
| bipartite | unknown to HOPS | exclusion |
| bipartite number | unknown to HOPS | unknown to HOPS |
| bisection bandwidth | unknown to HOPS | exclusion |
| block | unknown to HOPS | exclusion |
| book thickness | unknown to HOPS | unknown to HOPS |
| boolean width | unknown to HOPS | unknown to HOPS |
| bounded components | upper bound | exclusion |
| boxicity | unknown to HOPS | unknown to HOPS |
| branch width | upper bound | unknown to HOPS |
| c-closure | unknown to HOPS | exclusion |
| carving-width | upper bound | exclusion |
| chordal | unknown to HOPS | exclusion |
| chordality | unknown to HOPS | unknown to HOPS |
| chromatic number | unknown to HOPS | unknown to HOPS |
| clique cover number | unknown to HOPS | exclusion |
| clique-tree-width | unknown to HOPS | unknown to HOPS |
| clique-width | unknown to HOPS | unknown to HOPS |
| cluster | unknown to HOPS | exclusion |
| co-cluster | unknown to HOPS | exclusion |
| cograph | unknown to HOPS | exclusion |
| complete | unknown to HOPS | exclusion |
| connected | unknown to HOPS | unknown to HOPS |
| cutwidth | upper bound | exclusion |
| cycle | constant | exclusion |
| cycles | constant | exclusion |
| d-path-free | upper bound | exclusion |
| degeneracy | unknown to HOPS | unknown to HOPS |
| degree treewidth | upper bound | exclusion |
| diameter | unknown to HOPS | exclusion |
| diameter+max degree | upper bound | exclusion |
| disjoint cycles | constant | exclusion |
| distance to bipartite | unknown to HOPS | exclusion |
| distance to block | unknown to HOPS | exclusion |
| distance to bounded components | upper bound | exclusion |
| distance to chordal | unknown to HOPS | exclusion |
| distance to cluster | unknown to HOPS | exclusion |
| distance to co-cluster | unknown to HOPS | exclusion |
| distance to cograph | unknown to HOPS | exclusion |
| distance to complete | unknown to HOPS | exclusion |
| distance to edgeless | upper bound | exclusion |
| distance to forest | upper bound | exclusion |
| distance to interval | unknown to HOPS | exclusion |
| distance to linear forest | upper bound | exclusion |
| distance to maximum degree | unknown to HOPS | exclusion |
| distance to outerplanar | upper bound | exclusion |
| distance to perfect | unknown to HOPS | exclusion |
| distance to planar | unknown to HOPS | exclusion |
| distance to stars | upper bound | exclusion |
| domatic number | unknown to HOPS | unknown to HOPS |
| domination number | unknown to HOPS | exclusion |
| edge clique cover number | unknown to HOPS | exclusion |
| edge connectivity | unknown to HOPS | unknown to HOPS |
| edgeless | constant | exclusion |
| feedback edge set | upper bound | exclusion |
| feedback vertex set | upper bound | exclusion |
| forest | constant | exclusion |
| genus | unknown to HOPS | exclusion |
| girth | unknown to HOPS | exclusion |
| grid | unknown to HOPS | exclusion |
| h-index | unknown to HOPS | exclusion |
| inf-flip-width | unknown to HOPS | unknown to HOPS |
| interval | unknown to HOPS | exclusion |
| iterated type partitions | unknown to HOPS | exclusion |
| linear clique-width | unknown to HOPS | unknown to HOPS |
| linear forest | constant | exclusion |
| linear NLC-width | unknown to HOPS | unknown to HOPS |
| linear rank-width | unknown to HOPS | unknown to HOPS |
| maximum clique | unknown to HOPS | unknown to HOPS |
| maximum degree | unknown to HOPS | exclusion |
| maximum independent set | unknown to HOPS | exclusion |
| maximum induced matching | unknown to HOPS | exclusion |
| maximum leaf number | upper bound | exclusion |
| maximum matching | unknown to HOPS | exclusion |
| maximum matching on bipartite graphs | upper bound | exclusion |
| mim-width | unknown to HOPS | unknown to HOPS |
| minimum degree | unknown to HOPS | unknown to HOPS |
| mm-width | upper bound | unknown to HOPS |
| modular-width | unknown to HOPS | exclusion |
| module-width | unknown to HOPS | unknown to HOPS |
| neighborhood diversity | unknown to HOPS | exclusion |
| NLC-width | unknown to HOPS | unknown to HOPS |
| NLCT-width | unknown to HOPS | unknown to HOPS |
| odd cycle transversal | unknown to HOPS | exclusion |
| outerplanar | constant | exclusion |
| path | constant | exclusion |
| pathwidth | upper bound | exclusion |
| pathwidth+maxdegree | upper bound | exclusion |
| perfect | unknown to HOPS | exclusion |
| planar | unknown to HOPS | exclusion |
| radius-r flip-width | unknown to HOPS | unknown to HOPS |
| rank-width | unknown to HOPS | unknown to HOPS |
| shrub-depth | unknown to HOPS | unknown to HOPS |
| sim-width | unknown to HOPS | upper bound |
| star | constant | exclusion |
| stars | constant | exclusion |
| topological bandwidth | upper bound | exclusion |
| tree | constant | exclusion |
| treedepth | upper bound | exclusion |
| treelength | unknown to HOPS | unknown to HOPS |
| treewidth | upper bound | unknown to HOPS |
| twin-cover number | unknown to HOPS | exclusion |
| twin-width | unknown to HOPS | unknown to HOPS |
| vertex connectivity | unknown to HOPS | unknown to HOPS |
| vertex cover | upper bound | exclusion |
| vertex integrity | upper bound | exclusion |
Results
- unknown source
- treewidth upper bounds tree-independence number by a computable function
- tree-independence number upper bounds sim-width by a computable function