PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2012 | 32 | 3 | 517-533
Tytuł artykułu

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

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
32
Numer
3
Strony
517-533
Opis fizyczny
Daty
wydano
2012
otrzymano
2010-09-24
poprawiono
2011-03-16
zaakceptowano
2011-09-23
Twórcy
autor
  • Univ. Bordeaux, LaBRI, UMR 5800, F-33400 Talence, France
  • CNRS, LaBRI, UMR 5800, F-33400 Talence, France
Bibliografia
  • [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.
  • [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.
  • [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.
  • [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.
  • [5] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000).
  • [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
  • [7] J.W. Moon, Topics on Tournaments (Holt, Rinehart and Winston, New York, 1968).
  • [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.
  • [9] P. Ochem. Negative results on acyclic improper colorings, Proc. Euro Comb'05, Discrete Math. Theoret. Comput. Sci., Conference Volume AE (2005) 357-362.
  • [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.
  • [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.
  • [12] É. Sopena, Oriented graph coloring, Discrete Math. 229 (2001) 359-369, doi: 10.1016/S0012-365X(00)00216-8.
  • [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] D.R. Wood, On the oriented chromatic number of dense graphs, Contributions to Discrete Math. 2 (2007) 145-152.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1624
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.