Strong Oriented Chromatic Number of Planar Graphs without Cycles of Specific Lengths - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2007

Strong Oriented Chromatic Number of Planar Graphs without Cycles of Specific Lengths

Résumé

A strong oriented k-coloring of an oriented graph G is a homomorphism f from G to H having k vertices labelled by the k elements of an abelian additive group M, such that for any pairs of arcs uv and zt of G, we have f(v) - f(u) \neq -(f(t) - f(z))$. The strong oriented chromatic number is the smallest k such that G admits a strong oriented k-coloring. In this paper, we consider the following problem: Let i>=4 be an integer. Let G be an oriented planar graph without cycles of lengths 4 to i. What is the strong oriented chromatic number of G?

Dates et versions

lirmm-00196741 , version 1 (13-12-2007)

Identifiants

Citer

Mickael Montassier, Pascal Ochem, Alexandre Pinlou. Strong Oriented Chromatic Number of Planar Graphs without Cycles of Specific Lengths. LAGOS: Latin-American Algorithms, Graphs, and Optimization Symposium, Nov 2007, Puerto Varas, Chile. pp.27-32, ⟨10.1016/j.endm.2008.01.006⟩. ⟨lirmm-00196741⟩
102 Consultations
0 Téléchargements

Altmetric

Partager

More