chordality1993

https://www.doi.org/10.1002/jgt.3190170210

@article{chordality1993,
author = {Terry A. McKee and Edward R. Scheinerman},
doi = {10.1002/jgt.3190170210},
journaltitle = {Journal of Graph Theory},
number = {2},
pages = {221--232},
title = {On the chordality of a graph},
volume = {17},
year = {1993},
}

• 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 $k$ upper bounds chordality by $\mathcal O(k)$ – Corollary 4. For any graph $G$, $\mathrm{Chord}(G) \le \chi(G)$, the chromatic number of $G$.
• page 5 : treewidth $k$ upper bounds chordality by $\mathcal O(k)$ – Theorem 7. For any graph $G$, $\mathrm{Chord}(G) \le \tau(G)$.