𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the oriented chromatic number of grids

✍ Scribed by Guillaume Fertin; André Raspaud; Arup Roychowdhury

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
111 KB
Volume
85
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we focus on the oriented coloring of graphs. Oriented coloring is a coloring of the vertices of an oriented graph G without symmetric arcs such that (i) no two neighbors in G are assigned the same color, and (ii) if two vertices u and v such that (u, v) ∈ A(G) are assigned colors c(u) and c(v), then for any (z, t) ∈ A(G), we cannot have simultaneously c(z) = c(v) and c(t) = c(u). The oriented chromatic number of an unoriented graph G is the smallest number k of colors for which any of the orientations of G can be colored with k colors.

The main results we obtain in this paper are bounds on the oriented chromatic number of particular families of planar graphs, namely 2-dimensional grids, fat trees and fat fat trees.

📜 SIMILAR VOLUMES

The chromatic number of oriented graphs
The chromatic number of oriented graphs
✍ Sopena, Eric 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 2 views

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with

On the oriented chromatic index of orien
On the oriented chromatic index of oriented graphs
✍ Pascal Ochem; Alexandre Pinlou; Éric Sopena 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB

## Abstract A homomorphism from an oriented graph __G__ to an oriented graph __H__ is a mapping $\varphi$ from the set of vertices of __G__ to the set of vertices of __H__ such that $\buildrel {\longrightarrow}\over {\varphi (u) \varphi (v)}$ is an arc in __H__ whenever $\buildrel {\longrightarrow}

Acyclic and oriented chromatic numbers o
Acyclic and oriented chromatic numbers of graphs
✍ Kostochka, A. V.; Sopena, E.; Zhu, X. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB 👁 2 views

The oriented chromatic number χ o ( G) of an oriented graph G = (V, A) is the minimum number of vertices in an oriented graph H for which there exists a homomorphism of G to H. The oriented chromatic number χ o (G) of an undirected graph G is the maximum of the oriented chromatic numbers of all the

On the mean chromatic number
On the mean chromatic number
✍ Martin Anthony 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 209 KB

The mean chromatic number of a graph is a measure of the expected performance of the greedy vertex-colouring algorithm when each ordering of the vertices is equally likely. Some results on the value of the mean chromatic number and its asymptotic behaviour are presented.

Finite fields and the 1-chromatic number
Finite fields and the 1-chromatic number of orientable surfaces
✍ Vladimir P. Korzhik 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB

## Abstract The 1‐chromatic number χ~1~(__S__~__p__~) of the orientable surface __S__~__p__~ of genus __p__ is the maximum chromatic number of all graphs which can be drawn on the surface so that each edge is crossed by no more than one other edge. We show that if there exists a finite field of ord