4
$\begingroup$

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: <span class=\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!)

  • 0
    Yes I did, thanks.2012-08-01

2 Answers 2

0

This article may very well be the answer.

1

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

  • 0
    Sorry, neither am I.2012-08-01