Homomorphism bounds for oriented planar graphs

被引：19

作者：

Marshall, T. H. ^{[1
]}

机构：

[1] N Dakota State Univ, Dept Math, Fargo, ND 58105 USA

来源：

JOURNAL OF GRAPH THEORY | 2007年 / 55卷 / 03期

关键词：

oriented graph; planar graph; homomorphism; homomorphism bound; Paley tournament; Tromp graph;

D O I：

10.1002/jgt.20233

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

If C is a class of oriented graphs (directed graphs without opposite arcs), then an oriented graph is a homomorphism bound for C if there is a homomorphism from each graph in C to H. We find some necessary conditions for a graph to be a homomorphism bound for the class of oriented planar graphs and prove that such a graph must have maximum degree at least 16; thus there exists an oriented planar graph with oriented chromatic number at least 17. (c) 2007 Wiley Periodicals, Inc.

引用

页码：175 / 190

页数：16

共 14 条

[1]

ALBIERO V, 1995, P FPSAC95 FORM POW S, P11

[2] Homomorphisms of edge-colored graphs and Coxeter groups [J].

Alon, N ;

Marshall, TH .

JOURNAL OF ALGEBRAIC COMBINATORICS, 1998, 8 (01) :5-13

[3] ACYCLIC COLORINGS OF PLANAR GRAPHS [J].

BORODIN, OV .

DISCRETE MATHEMATICS, 1979, 25 (03) :211-236

[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]

Kostochka AV, 1997, J GRAPH THEOR, V24, P331, DOI 10.1002/(SICI)1097-0118(199704)24:4<331::AID-JGT5>3.0.CO

[6]

2-P

[7]

MARSHALL TH, DAM DIMATIA SERIES

[8] Colorings and girth of oriented planar graphs [J].

Nesetril, J ;

Raspaud, A ;

Sopena, E .

DISCRETE MATHEMATICS, 1997, 165 :519-530

[9] Colored homomorphisms of colored mixed graphs [J].

Nesetril, J ;

Raspaud, A .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 80 (01) :147-155

[10] GOOD AND SEMI-STRONG COLORINGS OF ORIENTED PLANAR GRAPHS [J].

RASPAUD, A ;

SOPENA, E .

INFORMATION PROCESSING LETTERS, 1994, 51 (04) :171-174

← 1 2 →