chordality1993

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