Good and semi-strong colorings of oriented planar graphs

A k-coloring of an oriented graph G = ( V, A) is an assignment c of one of the colors 1,2, ⋯, k to each vertex of the graph such that, for every arc ( x, y) of G, c( x) ≠ c( y). The k-coloring is good if for every arc ( x, y) of G there is no arc ( z, t) ϵ A such that c( x) = c( t) and c( y) = c( z)...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1994-08, Vol.51 (4), p.171-174
Main Authors: Raspaud, André, Sopena, Eric
Format: Article
Language:English
Subjects:
Applied sciences
Combinatorial problems
Computer science
control theory
systems
Exact sciences and technology
Graph coloring
Information retrieval. Graph
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A k-coloring of an oriented graph G = ( V, A) is an assignment c of one of the colors 1,2, ⋯, k to each vertex of the graph such that, for every arc ( x, y) of G, c( x) ≠ c( y). The k-coloring is good if for every arc ( x, y) of G there is no arc ( z, t) ϵ A such that c( x) = c( t) and c( y) = c( z). A k-coloring is said to be semi-strong if for every vertex x of G, c( z) ≠ c( t) for any pair { z, t} of vertices of N -( x). We show that every oriented planar graph has a good coloring using at most 5 x 2 4 colors and that every oriented planar graph G = ( V, A) with d -( x) ⩽ 3 for every x ϵ V has a good and semi-strong coloring using at most 4 x 5 x 2 4 colors.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(94)00088-3