My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
April 13th, 2010, 05:45 AM   #1
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.
ry. is offline  

  My Math Forum > College Math Forum > Applied Math

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 r-soy 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

Copyright © 2019 My Math Forum. All rights reserved.