Talk:Chordal graph

I think that written like this, the characterization of chordal graphs with intersection graphs is incorrect. If we read the sentence, we have the impression that chordal=subtree overlap, which is false. I guess it should be intersecting subtrees, and not overlaping subtrees. (see F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combinatorial Th. (B), 16(1974)47-56.)

I don't think the chromatic number of a chordal graph equals its clique number. Consider K_n and attach a dangling edge to one of its vertices. It is chordal, its clique number is n and its chromatic number is n+1. —Preceding unsigned comment added by 68.49.197.167 (talk) 05:10, 17 July 2008 (UTC)[reply]

You are mistaken. The dangling vertex may be given the same color as any of the other vertices except its neighbor, so only n colors are needed. —David Eppstein (talk) 05:15, 17 July 2008 (UTC)[reply]

Chord segments?

Must chords always be a single edge? What about the segment A-B-C in this graph? If this is not a chord, then what is it called?

  O-O-A-O-O
 /    |    \
O     B     O
 \    |    /
  O-O-C-O-O

If A-B-C is not a chord, then does that mean that all 3 cycles in this graph are chord-less, even though one of them is obviously divided by the other two? —Preceding unsigned comment added by 76.27.92.148 (talk) 12:50, 5 August 2010 (UTC)[reply]

Yes, chords have to be single edges, so your graph is not chordal. Which of the three cycles is the one that is divided by the other two? The graph structure does not specify an inside or an outside, so you could as easily have drawn path A-B-C around the outside and one of the other paths from A to C down the middle. I don't think there's a name for "graphs in which each cycle has a path between two non-consecutive vertices", although the case you've drawn where the whole graph consists of three paths between a pair of nodes is usually called a theta graph (because if you turn it sideways it has the shape of the greek letter theta, Θ). —David Eppstein (talk) 15:31, 5 August 2010 (UTC)[reply]

The reference for "A graph is chordal if and only if it has a perfect elimination" doesn't contain the word chordal nor perfect elimination, therefore my question if the reference is correct. Thanks for clarifying. 158.143.75.80 (talk) 15:16, 5 July 2014 (UTC)[reply]

That reference uses "rigid circuit graph" to mean a chordal graph (see middle of p.851) and states that a graph is a rigid circuit graph if and only if the process of deleting simplicial vertices succeeds in deleting all vertices (bottom of p.851), which is essentially the definition of an elimination ordering. So yes, it's a good reference. —David Eppstein (talk) 18:02, 5 July 2014 (UTC)[reply]