2 edited tags
1

# characterization of chordal graphs

I recently tried to prove the following characterization of chordal graphs, attributed to Fulkerson & Gross:

"A graph $G$ is chordal if and only if it has an ordering such that for all $v \in G$, all the neighbors of $v$ that precede it in the ordering form a clique."

I believe the wikipedia page calls this (or its reverse) a "perfect elimination ordering." In any case, my proof was harder than I expected and I ended up with the following strengthening:

"$G$ is chordal if and only if for any $v \in G$, we can find such an ordering of $G$ that starts with $v$."

I would like to know if this strengthening is:

1) known / obvious from the weaker theorem / obvious from folklore, or 2) wrong. =)

I can of course give a proof to anyone who is interested - it is just too long to fit here.

Best, -Yan