2
$\begingroup$

I'm working with graphs $G$ that have the following property: there is an ordering $v_1, \ldots, v_n$ of the vertices of $G$ such that the neighbours of $v_k$ among $\{v_1, \ldots, v_{k-1}\}$ induce a (possibly empty) clique. Examples include trees, indifference graphs, and quasi-threshold graphs.

Question: Is there a name for the class of graphs that satisfy this property?

[What I'm really using about the graphs is that there is an ordering of the vertices such that if the graph is revealed vertex-by-vertex in that order, then the sequence of (partial) chromatic polynomials forms a chain: earlier chromaric polynomials are divisors of later ones.]

$\endgroup$
  • 8
    $\begingroup$ Chordal graph? en.wikipedia.org/wiki/Chordal_graph - the reverse of your order is a perfect elimination ordering (I think). $\endgroup$ – Oliver Krüger Jun 7 '17 at 17:29
  • $\begingroup$ Thanks! It seems that I am working exactly with chordal graphs. $\endgroup$ – David Galvin Jun 7 '17 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.