Portal de Periódicos da CAPES

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

1999; Elsevier BV; Volume: 206; Issue: 1-3 Linguagem: Inglês

10.1016/s0012-365x(98)00393-8

1872-681X

O.V. Borodin, Alexandr Kostochka, Jaroslav Nešetřil, André Raspaud, Éric Sopena,

Retinoids in leukemia and cellular processes

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.