
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
April 13th, 2010, 05:45 AM  #1 
Newbie Joined: Apr 2010 Posts: 1 Thanks: 0  digraph: cycle of an even length and coloring the vertices
Prove that the following two conditions for a strongly connected directed graph G are equivalent: 1. G contains a directed cycle of an even length. 2. The vertices of G can be colored by 2 colors (each vertex receives one color) in such a way that for each vertex u there exists a directed edge (u, v) with v having the color different from the color of u. 

Tags 
coloring, cycle, digraph, length, vertices 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
which one is more efficience otto cycle or carnot cycle or d  rsoy  Physics  0  June 2nd, 2013 02:14 AM 
Conjecture on cycle length and primes : prime abc conjecture  miket  Number Theory  5  May 15th, 2013 05:35 PM 
Prove that a cycle of length n in Sk has order n  Elladeas  Abstract Algebra  1  February 4th, 2012 11:16 AM 
Coloring problem  Crouch  Algebra  3  July 4th, 2011 03:53 PM 
Prove G contains a cycle of length at least k+1  cxc001  Applied Math  1  October 1st, 2010 02:21 AM 