TY - JOUR
T1 - On the maximum average degree and the oriented chromatic number of a graph
AU - Borodin, O. V.
AU - Kostochka, A. V.
AU - Nešetřil, J.
AU - Raspaud, A.
AU - Sopena, E.
N1 - Funding Information:
∗Corresponding author. E-mail: [email protected]. 1On leave of absence from the Institute of Mathematics, Novosibirsk, 630090, Russia. With support from Engineering and Physical Sciences Research Council, UK, grant GR=K00561, and from the International Science Foundation, grant NQ4000. 2This work was partially supported by the Network DIMANET of the European Union and by the grant 96-01-01614 of the Russian Foundation for Fundamental Research. 3A part of this research was supported by GACR and GAUK grants and done during a visit of LaBRI, Universite Bordeaux I (France).
PY - 1999/8/28
Y1 - 1999/8/28
N2 - The oriented chromatic number o(H) of an oriented graph H is denned 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.
AB - The oriented chromatic number o(H) of an oriented graph H is denned 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.
UR - http://www.scopus.com/inward/record.url?scp=0002654721&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0002654721&partnerID=8YFLogxK
U2 - 10.1016/S0012-365X(98)00393-8
DO - 10.1016/S0012-365X(98)00393-8
M3 - Article
AN - SCOPUS:0002654721
SN - 0012-365X
VL - 206
SP - 77
EP - 89
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-3
ER -