Oriented Colorings of Partial 2-trees - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Information Processing Letters Année : 2008

Oriented Colorings of Partial 2-trees

Résumé

A homomorphism from an oriented graph G to an oriented graph H is an arc-preserving mapping f from V(G) to V(H), that is f(x)f(y) is an arc in H whenever xy is an arc in G. The oriented chromatic number of G is the minimum order of an oriented graph H such that G has a homomorphism to H. In this paper, we determine the oriented chromatic number of the class of partial 2-trees for every girth g >= 3. We also give an upper bound for the oriented chromatic number of planar graphs with girth at least 11.

Dates et versions

lirmm-00314715 , version 1 (27-08-2008)

Identifiants

Citer

Pascal Ochem, Alexandre Pinlou. Oriented Colorings of Partial 2-trees. Information Processing Letters, 2008, 108, pp.82-86. ⟨10.1016/j.ipl.2008.04.007⟩. ⟨lirmm-00314715⟩
93 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More