Oriented Colorings of Partial 2-trees - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Information Processing Letters Year : 2008

Oriented Colorings of Partial 2-trees

Abstract

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 and versions

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

Identifiers

Cite

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⟩
97 View
0 Download

Altmetric

Share

More