Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

Éric Sopena

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 3, page 517-533
  • ISSN: 2083-5892

Abstract

top
The oriented chromatic number of an oriented graph → G is the minimum order of an oriented graph → H such that → G admits a homomorphism to → H . The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph → U such that every orientation → G of G admits a homomorphism to → U . We give some properties of this parameter, derive some general upper bounds on the ordinary and upper oriented chromatic numbers of lexicographic, strong, Cartesian and direct products of graphs, and consider the particular case of products of paths.

How to cite

top

Éric Sopena. "Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs." Discussiones Mathematicae Graph Theory 32.3 (2012): 517-533. <http://eudml.org/doc/270820>.

@article{ÉricSopena2012,
abstract = {The oriented chromatic number of an oriented graph $^→G$ is the minimum order of an oriented graph $^→H$ such that $^→G$ admits a homomorphism to $^→H$. The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph $^→U$ such that every orientation $^→G$ of G admits a homomorphism to $^→U$. We give some properties of this parameter, derive some general upper bounds on the ordinary and upper oriented chromatic numbers of lexicographic, strong, Cartesian and direct products of graphs, and consider the particular case of products of paths.},
author = {Éric Sopena},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {product graph; oriented coloring; oriented chromatic number},
language = {eng},
number = {3},
pages = {517-533},
title = {Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs},
url = {http://eudml.org/doc/270820},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Éric Sopena
TI - Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 3
SP - 517
EP - 533
AB - The oriented chromatic number of an oriented graph $^→G$ is the minimum order of an oriented graph $^→H$ such that $^→G$ admits a homomorphism to $^→H$. The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph $^→U$ such that every orientation $^→G$ of G admits a homomorphism to $^→U$. We give some properties of this parameter, derive some general upper bounds on the ordinary and upper oriented chromatic numbers of lexicographic, strong, Cartesian and direct products of graphs, and consider the particular case of products of paths.
LA - eng
KW - product graph; oriented coloring; oriented chromatic number
UR - http://eudml.org/doc/270820
ER -

References

top
  1. [1] N.R. Aravind, N. Narayanan and C.R. Subramanian. Oriented colouring of some graph products, Discuss. Math. Graph Theory 31 (2011) 675-686, doi: 10.7151/dmgt.1572. Zbl1255.05073
  2. [2] N.R. Aravind and C.R. Subramanian. Forbidden subgraph colorings and the oriented chromatic number, in: Proc. 20th Int. Workshop on Combinatorial Algorithms, IWOCA'09, Lecture Notes in Comput. Sci. 5874 (2009) 60-71, doi: 10.1007/978-3-642-10217-2_9. Zbl1267.05111
  3. [3] L. Esperet and P. Ochem, Oriented colorings of 2-outerplanar graphs, Inform. Proc. Letters 101 (2007) 215-219, doi: 10.1016/j.ipl.2006.09.007. Zbl1185.05059
  4. [4] G. Fertin, A. Raspaud and A. Roychowdhury, On the oriented chromatic number of grids, Inform. Proc. Letters 85 (2003) 261-266, doi: 10.1016/S0020-0190(02)00405-2. Zbl1173.68604
  5. [5] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000). 
  6. [6] A.V. Kostochka, É. Sopena and X. Zhu, Acyclic and oriented chromatic numbers of graphs, J. Graph Theory 24 (1997) 331-340, doi: 10.1002/(SICI)1097-0118(199704)24:4<331::AID-JGT5>3.0.CO;2-P Zbl0873.05044
  7. [7] J.W. Moon, Topics on Tournaments (Holt, Rinehart and Winston, New York, 1968). Zbl0191.22701
  8. [8] P. Ochem, Oriented colorings of triangle-free planar graphs, Inform. Proc. Letters 92 (2004) 71-76, doi: 10.1016/j.ipl.2004.06.012. Zbl1173.68593
  9. [9] P. Ochem. Negative results on acyclic improper colorings, Proc. Euro Comb'05, Discrete Math. Theoret. Comput. Sci., Conference Volume AE (2005) 357-362. Zbl1192.05056
  10. [10] A. Pinlou and É. Sopena, Oriented vertex and arc colorings of outerplanar graphs, Inform. Proc. Letters 100 (2006) 97-104, doi: 10.1016/j.ipl.2006.06.012. Zbl1185.05064
  11. [11] A. Raspaud and É. Sopena, Good and semi-strong colorings of oriented planar graphs, Inform. Proc. Letters 51 (1994) 171-174, doi: 10.1016/0020-0190(94)00088-3. Zbl0806.05031
  12. [12] É. Sopena, Oriented graph coloring, Discrete Math. 229 (2001) 359-369, doi: 10.1016/S0012-365X(00)00216-8. Zbl0971.05039
  13. [13] É. Sopena and L. Vignal, A note on the oriented chromatic number of graphs with maximum degree three, Research Report (1996), http://www.labri.fr/perso/sopena/. 
  14. [14] D.R. Wood, On the oriented chromatic number of dense graphs, Contributions to Discrete Math. 2 (2007) 145-152. Zbl1203.05061

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.