Oriented Colorings of Partial 2-trees

Pascal Ochem 1 Alexandre Pinlou 2, *
* Corresponding author
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00314715
Contributor : Alexandre Pinlou <>
Submitted on : Wednesday, August 27, 2008 - 4:15:03 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Links full text

Identifiers

Citation

Pascal Ochem, Alexandre Pinlou. Oriented Colorings of Partial 2-trees. Information Processing Letters, Elsevier, 2008, 108, pp.82-86. ⟨10.1016/j.ipl.2008.04.007⟩. ⟨lirmm-00314715⟩

Share

Metrics

Record views

186