Re: searching an example for the road coloring conjecture, degree 2

Gerry Myerson wrote:
 > In article <drnu1v$32u$1@xxxxxxxxxxxxxxxx>,
 >  klaus hoffmann <nospam@xxxxxxxxxxxx> wrote:
 >
 >
 >>The road coloring problem/conjecture (degree 2) states that a strongly
 >>connected directed graph with outdegree 2 admits an edge coloring such
 >>that synchronizing words exist if the lcd of all (directed)
 >>cycle-lengths is 1:
 >>
 >>Carbone (1999) gives a solution if there are 2 coprime edge-disjoint
 >>cycles. I developed an algorithm for the general case and up to 30-60
 >>vertices, but I could not find a difficult example, i.e. a graph where
 >>the smallest coprime cycle set has at least 3 elements.
 >>Preliminary tests indicate that there is no such graph with <= 30
 >>vertices and a hamiltonian path.
 >>I would be grateful for a difficult example.
 >
 >
 > I may not fully understand the situation, but here goes:
 >
 > Consider a graph with a 6-cycle that shares one edge with a 10-cycle
 > that shares one edge with a 15-cycle. All told, 27 vertices and
 > 29 edges. Orient the edges so the thing is Hamiltonian. 25 of the
 > vertices have outdegree 1; add an edge joining each of these vertices
 > to itself.
 >
Loops or parallel edges are forbidden; a loop is counted as an 
(effectively) coprime cycle. The example I am searching need not have an 
hamiltonian path. I restricted my search to those because I tried to get 
cycles with as many prime factors as possible to avoid pairwise 
coprimality. I tried simple regular structures by joining equal chords; 
the problem is: we get a 6-cycle using a chord of length 5; joining 
three of them in a 15-hamcyc gives a  3 cycle.

Thank you very much.
Klaus Hoffmann

.

Relevant Pages

  • counting cycles
    ... :> its meaning is perfectly clear and non-controversial. ... If you try to graph it, ... Except that this cycle IS infinite. ... It's hard to know what you even COULD mean by an infinite cycle. ...
    (sci.logic)
  • Re: Finding Euler paths..
    ... > Euler path in a graph taking input as the edges. ... check that there can exist a euler path in the graph. ... [For a Euler cycle, find any old cycle to start ... So, our original path shares no vertices with the first cycle, so we ...
    (comp.programming)
  • Re: Shortest path algorithm in digraph with multiple goals?
    ... > lot of red edges (thus your solution will produce a huge graph). ... graph traversal algorithms. ... arcs" can occur in any cycle. ... which there have been 'k' previous traversals of the "counted" arcs. ...
    (comp.programming)
  • Re: Shortest path algorithm in digraph with multiple goals?
    ... > lot of red edges (thus your solution will produce a huge graph). ... graph traversal algorithms. ... arcs" can occur in any cycle. ... which there have been 'k' previous traversals of the "counted" arcs. ...
    (comp.theory)
  • Re: searching an example for the road coloring conjecture, degree 2
    ... > The road coloring problem/conjecture states that a strongly ... > connected directed graph with outdegree 2 admits an edge coloring such ...
    (sci.math.research)