Title of article :
Homomorphisms and edge-colourings of planar graphs
Author/Authors :
Naserasr، نويسنده , , Reza، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2007
Pages :
7
From page :
394
To page :
400
Abstract :
We conjecture that every planar graph of odd-girth 2 k + 1 admits a homomorphism to the Cayley graph C ( Z 2 2 k + 1 , S 2 k + 1 ) , with S 2 k + 1 being the set of ( 2 k + 1 ) -vectors with exactly two consecutive 1ʹs in a cyclic order. This is an strengthening of a conjecture of T. Marshall, J. Nešetřil and the author. Our main result is to show that this conjecture is equivalent to the corresponding case of a conjecture of P. Seymour, stating that every planar ( 2 k + 1 ) -graph is ( 2 k + 1 ) -edge-colourable.
Keywords :
planarity , Clebsch graph , Homomorphisms , edge-colouring
Journal title :
Journal of Combinatorial Theory Series B
Serial Year :
2007
Journal title :
Journal of Combinatorial Theory Series B
Record number :
1527807
Link To Document :
بازگشت