On the maximum average degree and the oriented chromatic number of a graph

被引：71

作者：

Borodin, OV

Kostochka, AV

Nesetril, J

Raspaud, A

Sopena, E

机构：

[1] Univ Nottingham, Dept Math, Nottingham NG7 2RD, England

[2] Russian Acad Sci, Inst Math, Novosibirsk 630090, Russia

[3] Charles Univ, Dept Appl Math, CR-11800 Prague, Czech Republic

[4] Univ Bordeaux 1, LABRI, F-33405 Talence, France

来源：

DISCRETE MATHEMATICS | 1999年 / 206卷 / 1-3期

基金：

英国工程与自然科学研究理事会;

关键词：

D O I：

10.1016/S0012-365X(98)00393-8

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The oriented chromatic number o(H) of an oriented graph H is defined as the minimum order of an oriented graph H' such that H has a homomorphism to H'. The oriented chromatic number o(G) of an undirected graph G is then defined as the maximum oriented chromatic number of its orientations. In this paper we study the links between o(G) and mad(G) defined as the maximum average degree of the subgraphs of G. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：77 / 89

页数：13

共 21 条

[1] EVERY PLANAR MAP IS 4 COLORABLE [J].