Homomorphisms from sparse graphs with large girth

被引：46
作者：
Borodin, OV [1 ]
Kim, SJ
Kostochka, AV
West, DB
机构：
[1] Inst Math, Novosibirsk 630090, Russia
[2] Univ Illinois, Dept Math, Urbana, IL 61801 USA
来源：
JOURNAL OF COMBINATORIAL THEORY SERIES B | 2004年 / 90卷 / 01期
基金：
美国国家科学基金会;
关键词：
graph coloring; graph homomorphism; planar graph; circular coloring; oriented coloring; discharging; t-Nice graphs;
D O I：
10.1016/S0095-8956(03)00081-9
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that planar graph with girth at least 20t-2/3 has circular chromatic number at most 2 + 1/t, 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. (C) 2003 Elsevier Inc. All rights reserved.
引用
收藏
页码：147 / 159
页数：13
相关论文
共 17 条
[1]   Homomorphisms of edge-colored graphs and Coxeter groups [J].
Alon, N ;
Marshall, TH .
JOURNAL OF ALGEBRAIC COMBINATORICS, 1998, 8 (01) :5-13
[2]   A NOTE ON THE STAR CHROMATIC NUMBER [J].
BONDY, JA ;
HELL, P .
JOURNAL OF GRAPH THEORY, 1990, 14 (04) :479-482
[3]   On universal graphs for planar oriented graphs of a given girth [J].
Borodin, OV ;
Kostochka, AV ;
Nesetril, J ;
Raspaud, A ;
Sopena, E .
DISCRETE MATHEMATICS, 1998, 188 (1-3) :73-85
[4]   On the maximum average degree and the oriented chromatic number of a graph [J].
Borodin, OV ;
Kostochka, AV ;
Nesetril, J ;
Raspaud, A ;
Sopena, E .
DISCRETE MATHEMATICS, 1999, 206 (1-3) :77-89
[5]  
DEVOS M, 2000, WORKSH FLOWS CYCL S
[6]   High-girth graphs avoiding a minor are nearly bipartite [J].
Galluccio, A ;
Goddyn, LA ;
Hell, P .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 83 (01) :1-14
[7]  
Grotzsch H., 1959, Halle-Wittenberg Math.-Natur. Reihe, V8, P109
[8]   On nice graphs [J].
Hell, P ;
Kostochka, AV ;
Raspaud, A ;
Sopena, E .
DISCRETE MATHEMATICS, 2001, 234 (1-3) :39-51
[9]  
Jaeger F., 1984, North-Holland, V37, P391
[10]  
Klostermeyer W, 2000, J GRAPH THEOR, V33, P109, DOI 10.1002/(SICI)1097-0118(200002)33:2<109::AID-JGT5>3.0.CO
12