Portal de Periódicos da CAPES

Homomorphisms from sparse graphs with large girth

2003; Elsevier BV; Volume: 90; Issue: 1 Linguagem: Inglês

10.1016/s0095-8956(03)00081-9

1096-0902

O. V. Borodin, S.-J. Kim, Alexandr Kostochka, Douglas B. West,

Graph Labeling and Dimension Problems

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.