# Graphs with a unique $3$-path free acyclic orientation up to isomorphism.

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:

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!)

-
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$.

-
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