Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Graphs and Combinatorics Year : 2014

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

Pascal Ochem

Abstract

A graph is planar if it can be embedded on the plane without edge-crossings. 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 [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 [Esperet, L. and Ochem, P. Oriented colouring of 2-outerplanar graphs, Inform. Process. Lett., vol. 101(5), 215-219, 2005].
No file

Dates and versions

lirmm-00780910 , version 1 (25-01-2013)

Identifiers

Cite

Pascal Ochem, Alexandre Pinlou. Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs. Graphs and Combinatorics, 2014, 30 (2), pp.439-453. ⟨10.1007/s00373-013-1283-2⟩. ⟨lirmm-00780910⟩
149 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More