On the oriented chromatic number of grids |
| |
Authors: | Guillaume Fertin André Raspaud |
| |
Affiliation: | a IRIN UPRES-EA 2157, Université de Nantes, 2 rue de la Houssinière, BP 92208, F44322 Nantes Cedex 3, France b LaBRI U.M.R. 5800, Université Bordeaux I, 351 Cours de la Libération, F33405 Talence Cedex, France c Oracle India Private Limited, Hi-Tec City, Madhapur, Hyderabad 500081, India |
| |
Abstract: | 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. |
| |
Keywords: | Graphs Oriented coloring Proper coloring Combinatorial problems |
本文献已被 ScienceDirect 等数据库收录! |
|