0
$\begingroup$

I am currently interested in learning more about perfect graphs, and perfectly orderable graphs, however some of the basic concepts are escaping me, and I am simply unable to wrap my head around some of the definitions and examples I am facing. I understand that, for example, a perfectly orderable graph is one where its vertices may be ordered in such a way that allows it to be optimally colored via a greedy coloring algorithm - https://en.wikipedia.org/wiki/Perfectly_orderable_graph.

Here is another definition:

"Given an ordered graph (G, < ), the ordering < is called perfect (Chvátal, V., Perfectly ordered graphs, Perfect graphs, Ann. Discrete Math. 21, 63-65 (1984). ZBL0559.05055.) if for each induced ordered subgraph (H, < ) the greedy algorithm produces an optimal colouring of H. The graphs admitting a perfect ordering are called perfectfy orderable. An obstruction in an ordered graph is a chordless path with four vertices abcd such that a <b and d <c. It is easily seen that a perfectly ordered graph has no obstruction. Chvatal has shown that this condition is also sufficient: a graph is perfectly orderable if and only if it admits an obstruction-free ordering" (Hoàng, Chín T.; Maffray, Frédéric; Olariu, Stephan; Preissmann, Myriam, A charming class of perfectly orderable graphs, Discrete Math. 102, No. 1, 67-74 (1992). ZBL0776.05091.)

Nevertheless, I am struggling to understand how to determine that a graph is perfectly orderable (or not perfectly orderable). For example a perfectly orderable graph would be (with a perfect ordering, for example of c<d<e<b<a, and the only two induced subgraphs of 4 vertices, being: abcd & aedc):

And a non-perfectly orderable graph, which does not exhibit a perfect ordering: enter image description here

In short, why is the first one perfectly orderable but not the other?

$\endgroup$

1 Answer 1

1
$\begingroup$

For the first one, we can check that the ordering given is perfect: $c<d<e<b<a$. This can be done directly by checking all induced subgraphs (only subgraphs on at least $4$ vertices need to be checked, and there's $6$ of those). Or, we could look at the chordless paths in the graph, and check that they don't form obstructions:

  • $a,b,c,d$ doesn't because $a>b$ in the ordering (also because $d>c$).
  • $a,e,d,c$ doesn't because $a>e$ in the ordering.
  • No other paths are chordless.

For the second one, we want to show that no ordering is perfect, which is easiest to do by showing that there's always an obstruction. In principle, there's $5!$ orderings to check, but we can save on duplicated effort by making use of the symmetry.

Without loss of generality, $a$ is first in the ordering (because the vertices are all identical, and one of them has to be first). Then:

  • If $c > d$, then $a,b,c,d$ is an obstruction, because $a<b$ and $d<c$.
  • If $c < d$, then $a,e,d,c$ is an obstruction, because $a<e$ and $c<d$.

So either way, there is an obstruction.

$\endgroup$
5
  • $\begingroup$ Thanks for your explanation. But why can't your method for proving the pentagon as not perfectly orderable, be applied to the first graph as well? Aren't these two chordless chains symmetric as well? $\endgroup$
    – h3ab74
    Nov 28, 2020 at 21:48
  • 1
    $\begingroup$ In the first graph, we can't assume that the ordering starts with $a$, because not all the vertices are identical. $\endgroup$ Nov 28, 2020 at 21:49
  • $\begingroup$ Also, isn't one property of perfect graphs that: χ(G') = ω(G') ⱯG' in G? And given that the 2nd graph is a subgraph of the first, hence the first is not perfect? $\endgroup$
    – h3ab74
    Nov 28, 2020 at 21:50
  • 1
    $\begingroup$ That property holds for all induced subgraphs $G'$, and the second graph is not an induced subgraph of the first. $\endgroup$ Nov 28, 2020 at 22:20
  • $\begingroup$ Thank you so much. Have yourself a fantastic weekend. $\endgroup$
    – h3ab74
    Nov 28, 2020 at 22:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.