characterization of chordal graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T13:45:15Z http://mathoverflow.net/feeds/question/20039 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/20039/characterization-of-chordal-graphs characterization of chordal graphs yanzhang 2010-04-01T05:57:02Z 2010-04-01T20:37:30Z <p>I recently tried to prove the following characterization of <a href="http://en.wikipedia.org/wiki/Chordal_graph" rel="nofollow">chordal graphs</a>, attributed to Fulkerson &amp; Gross:</p> <p>"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."</p> <p>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: </p> <p>"$G$ is chordal if and only if for any $v \in G$, we can find such an ordering of $G$ that starts with $v$."</p> <p>I would like to know if this strengthening is:</p> <p>1) known / obvious from the weaker theorem / obvious from folklore, or 2) wrong. =)</p> <p>I can of course give a proof to anyone who is interested - it is just too long to fit here.</p> <p>Best, -Yan</p> http://mathoverflow.net/questions/20039/characterization-of-chordal-graphs/20041#20041 Answer by yanzhang for characterization of chordal graphs yanzhang 2010-04-01T06:18:18Z 2010-04-01T06:18:18Z <p>Wow. Scary how I've failed to do this until I ask the question on MO, and then immediately get the idea.</p> <p>Here's a proof, assuming the weaker version of the theorem is true:</p> <p>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.</p> <p>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$.</p> <p>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.</p> <p>-Yan</p> http://mathoverflow.net/questions/20039/characterization-of-chordal-graphs/20043#20043 Answer by David Eppstein for characterization of chordal graphs David Eppstein 2010-04-01T06:36:33Z 2010-04-01T06:36:33Z <p>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.</p>