Title of article :
Homomorphisms from sparse graphs with large girth
Author/Authors :
Borodin، نويسنده , , O.V. and Kim، نويسنده , , S.-J. and Kostochka، نويسنده , , A.V. and West، نويسنده , , D.B.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2004
Pages :
13
From page :
147
To page :
159
Abstract :
We show that a planar graph with girth at least 20t−23 has circular chromatic number at most 2+1t, improving earlier results. This follows from a general result establishing homomorphisms into special targets for graphs with given girth and given maximum average degree. Other applications concern oriented chromatic number and homomorphisms into mixed graphs with colored edges.
Keywords :
t-Nice graphs , graph coloring , Planar graph , Graph homomorphism , Circular coloring , Oriented coloring , Discharging
Journal title :
Journal of Combinatorial Theory Series B
Serial Year :
2004
Journal title :
Journal of Combinatorial Theory Series B
Record number :
1527360
Link To Document :
بازگشت