chordality

tags: covering edges

equivalent to: chordality

Relations

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)$.
• 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