Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\Gamma$ be a simple, $3$-colorable graph such that, up to isomorphism, there exists exactly one acyclic orientation of $\Gamma$ that does not contain a directed 3-path. (To be clear, when I say $3$-path, I mean three edges, four vertices.) I require that $\Gamma$ is $3$-colorable so that at least one such orientation exists (this is an if and only if).

The $5$-cycle is an example of a graph with this property. Up to isomorphism, the only orientation that meets this requirement is the following:

Example: $\overset{\rightharpoonup}{C_5}$.

I have a few questions about these:

I. Can graphs like this be characterized in some other way? What is it that makes these guys only have one orientation?

There may be something to the twisted orbital chromatic polynomial, described briefly at the end of document. Perhaps this could somehow be adapted to exclude orientations with induced $3-$paths.

II. Are there any more of these other than $C_5$, apart from trivial examples on less than $4$ vertices?

Originally I thought these would constitute an infinite family of graphs, but to my surprise I have been unable to think of even one other example. Does the condition preclude graphs above a certain order?

III. Can anyone help me construct an algorithm to check for graphs of this type on $6$ or more vertices?

I can use MAGMA and Mathematica for the language, or $C$ if that's what you want. (Though that might be a bit low level for these purposes!)

share|cite|improve this question
Where it says "at least one orientation", I think you mean "at least one such orientation"? – joriki Aug 1 '12 at 1:11
Yes I did, thanks. – Alexander Gruber Aug 1 '12 at 7:38

You might find an answer in Stanley, Acyclic orientations of graphs, Discrete Math 5 (1973) 171-178, available here. Stanley proves, among other things, that if $G$ is a graph with $p$ vertices, and $\chi(x)$ is the chromatic polynomial of $G$, then $(-1)^p\chi(-1)$ is the number of acyclic orientations of $G$.

share|cite|improve this answer
I saw this article while researching the problem and considered including it in my post. I am unsure how to reduce this to insist that the orientation is unique up to isomorphism. Further I do not know how exactly to interpret the chromatic polynomial under the conditions that the graphs are triangle free. Any advice would be appreciated; I am not a graph theorist. – Alexander Gruber Aug 1 '12 at 2:06
Sorry, neither am I. – Gerry Myerson Aug 1 '12 at 3:06
up vote 0 down vote accepted

This article may very well be the answer.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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