Colorings and girth of oriented planar graphs
type: Item
instance of: scholarly article
title: Colorings and girth of oriented planar graphs
zbMATH Open document ID: 0873.05042
DOI: 10.1016/S0012-365X(96)00198-7
author: Éric Sopena
author: J. Nešetřil
author: André Raspaud
published in: Discrete Mathematics
publication date: 1997-10-26T00:00:00Z
review text: Let \(G=(V,E)\) and \(H=(V',E')\) be graphs (possibly digraphs). A homomorphism from \(G\) to \(H\) is any mapping \(f:V\to V'\) satisfying \([x,y]\in E\Rightarrow [f(x),f(y)]\in E'.\) Here the brackets on both sides of the implication mean the same thing: either an edge or an arc. The existence of a homomorphism from \(G\) to \(H\) is denoted by \(G\to H\). The following two problems are considered: (A) The oriented coloring problem. Given an oriented graph \(G=(V,A)\), find the smallest number of vertices of an oriented graph \(H\) for which \(G\to H\). This number, denoted by \(\chi(\vec G)\), is called the oriented chromatic number of \(G\). (Note that this is the same as the ordinary chromatic number if we consider symmetric digraphs as target digraphs.) (B) The girth problem. Given an integer \(g>2\), determine the quantity \[ \chi(\vec g)= \max\{\chi(\vec G)\mid G\text{ is planar and has girth }g\}. \] It is shown that every orientation of any large girth planar graph has oriented chromatic number at most 5. Furthermore, the authors classify those digraphs on 3, 4 and 5 vertices which color (i.e. admit a homomorphism from) all large girth oriented planar graphs.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1019120
zbMATH Keywords: homomorphism
zbMATH Keywords: coloring
zbMATH Keywords: oriented chromatic number
zbMATH Keywords: digraphs
zbMATH Keywords: girth
zbMATH Keywords: planar graph
reviewed by: Jørgen Bang-Jensen
MaRDI profile type: Publication
cites work: Every planar map is four colorable
cites work: The effect of two cycles on the complexity of colourings by directed graphs
cites work: On acyclic colorings of planar graphs
cites work: Acyclic colorings of planar graphs
cites work: Universality of \(A\)-mote graphs
cites work: On the complexity of H-coloring
cites work: Duality and Polynomial Testing of Tree Homomorphisms
cites work: Q4878664
cites work: Some new good characterizations for directed graphs
cites work: Q4200238
cites work: Acyclic and oriented chromatic numbers of graphs
cites work: Colorings and interpretations: a connection between graphs and grammar forms
cites work: Q4894618
cites work: Good and semi-strong colorings of oriented planar graphs
cites work: On the oriented game chromatic number
cites work: Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
Wikidata QID: Q126529477
description: scientific article; zbMATH DE number 1019120