chordality
tags: covering edges
Relations
| Other | Relation from | Relation to | |
|---|---|---|---|
| acyclic chromatic number | ■ | upper bound | exclusion |
| arboricity | ■ | upper bound | exclusion |
| average degree | ■ | exclusion | exclusion |
| average distance | ■ | exclusion | exclusion |
| bandwidth | ■ | upper bound | exclusion |
| bipartite | ■ | upper bound | exclusion |
| bipartite number | ■ | exclusion | unknown to HOPS |
| bisection bandwidth | ■ | exclusion | exclusion |
| block | ■ | upper bound | exclusion |
| book thickness | ■ | upper bound | exclusion |
| boolean width | ■ | exclusion | exclusion |
| bounded components | ■ | upper bound | exclusion |
| boxicity | ■ | upper bound | exclusion |
| branch width | ■ | upper bound | exclusion |
| c-closure | ■ | unknown to HOPS | exclusion |
| carving-width | ■ | upper bound | exclusion |
| chordal | ■ | upper bound | exclusion |
| chordality | ■ | equal | equal |
| chromatic number | ■ | upper bound | exclusion |
| clique cover number | ■ | exclusion | exclusion |
| clique-tree-width | ■ | unknown to HOPS | exclusion |
| clique-width | ■ | exclusion | exclusion |
| cluster | ■ | upper bound | exclusion |
| co-cluster | ■ | upper bound | exclusion |
| cograph | ■ | upper bound | exclusion |
| complete | ■ | upper bound | exclusion |
| connected | ■ | unknown to HOPS | exclusion |
| contraction complexity | ■ | upper bound | exclusion |
| cutwidth | ■ | upper bound | exclusion |
| cycle | ■ | upper bound | exclusion |
| cycles | ■ | upper bound | exclusion |
| d-path-free | ■ | upper bound | exclusion |
| degeneracy | ■ | upper bound | exclusion |
| degree treewidth | ■ | upper bound | exclusion |
| diameter | ■ | exclusion | exclusion |
| diameter+max degree | ■ | upper bound | exclusion |
| disconnected | ■ | unknown to HOPS | exclusion |
| disjoint cycles | ■ | upper bound | exclusion |
| distance to bipartite | ■ | upper bound | exclusion |
| distance to block | ■ | upper bound | exclusion |
| distance to bounded components | ■ | upper bound | exclusion |
| distance to chordal | ■ | upper bound | exclusion |
| distance to cluster | ■ | upper bound | exclusion |
| distance to co-cluster | ■ | upper bound | exclusion |
| distance to cograph | ■ | upper bound | exclusion |
| distance to complete | ■ | upper bound | exclusion |
| distance to disconnected | ■ | exclusion | exclusion |
| distance to edgeless | ■ | upper bound | exclusion |
| distance to forest | ■ | upper bound | exclusion |
| distance to interval | ■ | upper bound | exclusion |
| distance to linear forest | ■ | upper bound | exclusion |
| distance to maximum degree | ■ | upper bound | exclusion |
| distance to outerplanar | ■ | upper bound | exclusion |
| distance to perfect | ■ | exclusion | exclusion |
| distance to planar | ■ | upper bound | exclusion |
| distance to stars | ■ | upper bound | exclusion |
| domatic number | ■ | exclusion | exclusion |
| domination number | ■ | exclusion | exclusion |
| edge clique cover number | ■ | upper bound | exclusion |
| edge connectivity | ■ | exclusion | exclusion |
| edgeless | ■ | upper bound | exclusion |
| feedback edge set | ■ | upper bound | exclusion |
| feedback vertex set | ■ | upper bound | exclusion |
| forest | ■ | upper bound | exclusion |
| genus | ■ | upper bound | exclusion |
| girth | ■ | exclusion | exclusion |
| grid | ■ | upper bound | exclusion |
| h-index | ■ | upper bound | exclusion |
| inf-flip-width | ■ | exclusion | exclusion |
| interval | ■ | upper bound | exclusion |
| iterated type partitions | ■ | unknown to HOPS | exclusion |
| linear clique-width | ■ | unknown to HOPS | exclusion |
| linear forest | ■ | upper bound | exclusion |
| linear NLC-width | ■ | unknown to HOPS | exclusion |
| linear rank-width | ■ | unknown to HOPS | exclusion |
| maximum clique | ■ | unknown to HOPS | exclusion |
| maximum degree | ■ | upper bound | exclusion |
| maximum independent set | ■ | exclusion | exclusion |
| maximum induced matching | ■ | exclusion | exclusion |
| maximum leaf number | ■ | upper bound | exclusion |
| maximum matching | ■ | upper bound | exclusion |
| maximum matching on bipartite graphs | ■ | upper bound | exclusion |
| mim-width | ■ | exclusion | unknown to HOPS |
| minimum degree | ■ | exclusion | exclusion |
| mm-width | ■ | upper bound | exclusion |
| modular-width | ■ | exclusion | exclusion |
| module-width | ■ | exclusion | exclusion |
| neighborhood diversity | ■ | upper bound | exclusion |
| NLC-width | ■ | exclusion | exclusion |
| NLCT-width | ■ | unknown to HOPS | exclusion |
| odd cycle transversal | ■ | upper bound | exclusion |
| outerplanar | ■ | upper bound | exclusion |
| path | ■ | upper bound | exclusion |
| pathwidth | ■ | upper bound | exclusion |
| pathwidth+maxdegree | ■ | upper bound | exclusion |
| perfect | ■ | unknown to HOPS | exclusion |
| planar | ■ | upper bound | exclusion |
| radius-r flip-width | ■ | exclusion | unknown to HOPS |
| rank-width | ■ | exclusion | exclusion |
| shrub-depth | ■ | unknown to HOPS | exclusion |
| sim-width | ■ | exclusion | unknown to HOPS |
| size | ■ | upper bound | exclusion |
| star | ■ | upper bound | exclusion |
| stars | ■ | upper bound | exclusion |
| topological bandwidth | ■ | upper bound | exclusion |
| tree | ■ | upper bound | exclusion |
| tree-independence number | ■ | unknown to HOPS | unknown to HOPS |
| treedepth | ■ | upper bound | exclusion |
| treelength | ■ | exclusion | unknown to HOPS |
| treewidth | ■ | upper bound | exclusion |
| twin-cover number | ■ | upper bound | exclusion |
| twin-width | ■ | exclusion | exclusion |
| vertex connectivity | ■ | exclusion | exclusion |
| vertex cover | ■ | upper bound | exclusion |
| vertex integrity | ■ | upper bound | exclusion |
Results
- 2022 Expanding the Graph Parameter Hierarchy by Tran
- page 16 : chordality – The chordality of a graph $G$ is the minimum amount of chordal graphs required, such that their intersection (ed: fixed typo) results in $G$.
- page 30 : bounded modular-width does not imply bounded chordality – Theorem 4.16. Modular-width is incomparable to Chordality.
- page 30 : bounded chordality does not imply bounded modular-width – Theorem 4.16. Modular-width is incomparable to Chordality.
- 2019 The Graph Parameter Hierarchy by Sorge
- page 9 : boxicity upper bounds chordality by a linear function – Lemma 4.15 ([8,11]). The boxicity $b$ upper-bounds the chordality $c$. We have $c \le b$.
- page 9 : distance to chordal upper bounds chordality by a linear function – (ed: apparently goes as the lemma for ddist to interval and boxicity) Lemma 4.16. The distance $i$ to an interval graph upper bounds the boxicity $b$. We have $b \le i+1$.
- 1993 On the chordality of a graph by McKee, Scheinerman
- page 1 : chordality – The \emph{chordality} of a graph $G=(V,E)$ is defined as the minimum $k$ such that we can write $E=E_1,\cap\dots\cap E_k$ with each $(V,E_i)$ a chordal graph.
- page 2 : chromatic number upper bounds chordality by a linear function – Corollary 4. For any graph $G$, $\mathrm{Chord}(G) \le \chi(G)$, the chromatic number of $G$.
- page 5 : treewidth upper bounds chordality by a linear function – Theorem 7. For any graph $G$, $\mathrm{Chord}(G) \le \tau(G)$.
- assumed
- chordality is equivalent to chordality – assumed
- unknown source
- distance to cograph upper bounds chordality by a linear function
- Comparing Graph Parameters by Schröder
- page 19 : bounded clique cover number does not imply bounded chordality – Proposition 3.11
- page 19 : bounded distance to perfect does not imply bounded chordality – Proposition 3.11
- page 33 : bounded bisection bandwidth does not imply bounded chordality – Proposition 3.31
- page 36 : bounded average degree does not imply bounded chordality – Proposition 3.36