Road Coloring Problem

Author

Eric W. Weisstein
February 27, 2009

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/RoadColoringProblem.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/RoadColoringProblem.html.

©2009 Wolfram Research, Inc. except for portions noted otherwise

Figure

With[{rcp={{{1,2},{2,3},{3,1},{4,6},{5,4},{6,7},{7,2},{8,7}},{{1,5},{2,8},{3,4},{4,1},{5,6},{6,8},{7,3},{8,5}}}},ShowGraph[Graph[Flatten[{{#,EdgeColor->Red}&/@rcp[[1]],{#,EdgeColor->Blue}&/@rcp[[2]]},1],{{{0,0},VertexColor->Black},{{4,0},VertexColor->Green},{{2,1},VertexColor->Black},{{1,2},VertexColor->Yellow},{{0,4},VertexColor->Black},{{2,3},VertexColor->Black},{{3,2},VertexColor->Black},{{4,4},VertexColor->Black}}],EdgeDirection->On,EdgeStyle->{Arrowheads[.08]},ImageSize->250]/.Arrow[x_]:>Arrow[x,{0,.02}]]