characterization of chordal graphs - MathOverflow

characterization of chordal graphs

2010-04-01T05:57:02Z

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

Answer by yanzhang for characterization of chordal graphs

2010-04-01T06:18:18Z

Wow. Scary how I've failed to do this until I ask the question on MO, and then immediately get the idea.

Here's a proof, assuming the weaker version of the theorem is true:

Call such an ordering "good." Consider a minimal counterexample $M$ of size $n$ to our stronger claim: it must be chordal, has a good ordering, but does not have a good ordering starting at every vertex. However, every chordal graph of size less than $n$ has a good ordering starting at every vertex.

Since $M$ has some good ordering $T$, it has some vertex $v$ (the last one in $T$) such that all its neighbors form a clique. Remove this vertex to get $M'$. $M'$ is chordal (since chordality respects vertex deletion), so we can make a good ordering starting with any element in $M'$. Attach $v$ to the end. This ordering is obviously still good. Thus, we can make a good ordering starting with any vertex that is not $v$. So it suffices to make a good ordering starting with $v$.

To do this, consider the last vertex $w$ in $T \setminus v$ with the property that $w$ is not connected to the vertex $w'$ immediately following it in $T$. If $w$ doesn't exist, this just means $M$ is a clique, so any ordering is good and we have a good ordering starting with $v$. If $w$ exists, then notice that $w$ cannot be connected with any of the vertices after it in $T$; if it is, then pick the earliest such one $u \neq w'$, which is both connected to the vertex directly preceding it (not connected to $w$ by choice of $u$) and $w$, a contradiction on the ordering being good. Thus, $w$ is only connected with vertices preceding it. This means all of $w$'s neighbors form a clique. Hence, we can delete $w$, make a good ordering starting with $v$ of the rest, and append $w$ to the end. A winner is us.

-Yan

Answer by David Eppstein for characterization of chordal graphs

2010-04-01T06:36:33Z

It's known/obvious from the next few lines of the Wikipedia article stating that a LexBFS ordering (or its reverse, depending on your conventions) gives a perfect elimination ordering, since LexBFS can be made to start at any vertex.