Oriented colorings of triangle-free planar graphs

被引：18

作者：

Ochem, P ^{[1
]}

机构：

[1] Univ Bordeaux 1, LaBRI, F-33405 Talence, France

来源：

INFORMATION PROCESSING LETTERS | 2004年 / 92卷 / 02期

关键词：

combinatorial problems; oriented coloring; discharging;

D O I：

10.1016/j.ipl.2004.06.012

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The oriented colorings of triangle-free planar graphs and the use of the notation Pk for the class of planar graphs of girth at least k are discussed. An oriented triangle-free planar graph with oriented chromatic number at least 11 to prove the lower bound is exhibited. The tournament QR 59 and some of its properties are introduced. The upper bound of theorem is proved by showing that every triangle-free planar graph has a homomorphism to the Cayley graph QR59.

引用

页码：71 / 76

页数：6

共 8 条

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