episciences.org_418_20230328202624989
20230328202624989
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
01
10
2008
Vol. 10 no. 1
Strong Oriented Chromatic Number of Planar Graphs without Short Cycles
Mickael
Montassier
Pascal
Ochem
Alexandre
Pinlou
Let M be an additive abelian group. An Mstrongoriented coloring of an oriented graph G is a mapping f from V(G) to M such that f(u) <> j(v) whenever uv is an arc in G and f(v)−f(u) <> −(f(t)−f(z)) whenever uv and zt are two arcs in G. The strong oriented chromatic number of an oriented graph is the minimal order of a group M such that G has an Mstrongoriented coloring. This notion was introduced by Nesetril and Raspaud [Ann. Inst. Fourier, 49(3):10371056, 1999]. We prove that the strong oriented chromatic number of oriented planar graphs without cycles of lengths 4 to 12 (resp. 4 or 6) is at most 7 (resp. 19). Moreover, for all i ≥ 4, we construct outerplanar graphs without cycles of lengths 4 to i whose oriented chromatic number is 7.
01
10
2008
418
https://hal.science/lirmm00184811v1
10.46298/dmtcs.418
https://dmtcs.episciences.org/418

https://dmtcs.episciences.org/418/pdf

https://dmtcs.episciences.org/418/pdf