Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs

Pascal Ochem 1 Alexandre Pinlou 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A graph is planar if it can be embedded on the plane without edge-crossing. A graph is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the external face is outerplanar (i.e. with all its vertices on the external face). An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented graph H of order k. We prove that every oriented triangle-free planar graph has an oriented chromatic number at most 40, that improves the previous known bound of 47 due to Borodin and Ivanova [Borodin, O. V. and Ivanova, A. O., An oriented colouring of planar graphs with girth at least 4, Sib. Electron. Math. Reports, vol. 2, 239-249, 2005]. We also prove that every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bound of 67 due to Esperet and Ochem [Esperet, L. and Ochem, P. Oriented colouring of 2-outerplanar graphs, Inform. Process. Lett., vol. 101(5), 215-219, 2005].
Type de document :
Communication dans un congrès
Flavia Bonomo, Thomas Liebling, Javier Marenco, Jayme Szwarcfiter, Mario Valencia-Pabon. LAGOS'11: VI Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. 37, pp.123-128, 2011, Electronic Notes in Discrete Mathematics. 〈http://www-2.dc.uba.ar/lagos2011/〉. 〈10.1016/j.endm.2011.05.022〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00530543
Contributeur : Alexandre Pinlou <>
Soumis le : vendredi 29 octobre 2010 - 11:21:30
Dernière modification le : mardi 24 avril 2018 - 13:38:15
Document(s) archivé(s) le : dimanche 30 janvier 2011 - 02:49:34

Fichier

op10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Pascal Ochem, Alexandre Pinlou. Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs. Flavia Bonomo, Thomas Liebling, Javier Marenco, Jayme Szwarcfiter, Mario Valencia-Pabon. LAGOS'11: VI Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. 37, pp.123-128, 2011, Electronic Notes in Discrete Mathematics. 〈http://www-2.dc.uba.ar/lagos2011/〉. 〈10.1016/j.endm.2011.05.022〉. 〈lirmm-00530543〉

Partager

Métriques

Consultations de la notice

310

Téléchargements de fichiers

235