Oriented colouring of some graph products

N.R. Aravind ; N. Narayanan ; C.R. Subramanian

Discussiones Mathematicae Graph Theory, Tome 31 (2011), p. 675-686 / Harvested from The Polish Digital Mathematics Library

Résumé

We obtain some improved upper and lower bounds on the oriented chromatic number for different classes of products of graphs.

Détail

Publié le : 2011-01-01

Zbl 1255.05073

EUDML-ID : urn:eudml:doc:270980

Bibliographie

[000] [1] N.R. Aravind and C.R. Subramanian, Forbidden subgraph colorings and the oriented chromatic number, in: 4th International Workshop on Combinatorial Algorithms 4393 (2009) 477-488. | Zbl 1267.05111

[001] [2] O.V. Borodin, A.V. Kostochka, J. Nesetril, A. Raspaud and É. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. 206 (1999) 77-89, doi: 10.1016/S0012-365X(98)00393-8. | Zbl 0932.05033

[002] [3] O.V. Borodin, A.V. Kostochka, A. Raspaud and É. Sopena. Acyclic colouring of 1-planar graphs, Discrete Appl. Math. 114 (2001) 29-41, doi: 10.1016/S0166-218X(00)00359-0. | Zbl 0996.05053

[003] [4] B. Courcelle, The monadic second order logic of graphs. vi. on several representations of graphs by relational structures, Discrete Appl. Math. 54 (1994) 117-149, doi: 10.1016/0166-218X(94)90019-1. | Zbl 0809.03005

[004] [5] L. Esperet and P. Ochem, Oriented colorings of 2-outerplanar graphs, Information Processing Letters 101 (2007) 215-219, doi: 10.1016/j.ipl.2006.09.007. | Zbl 1185.05059

[005] [6] G. Fertin, A. Raspaud and A. Roychowdhury, On the oriented chromatic number of grids, Information Processing Letters 85 (2003) 261-266, doi: 10.1016/S0020-0190(02)00405-2. | Zbl 1173.68604

[006] [7] E. Fried, On homogeneous tournaments, Combinatorial Theory and its Applications 2 (1970) 467-476. | Zbl 0215.33704

[007] [8] P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications (28), 2004. | Zbl 1062.05139

[008] [9] T. Herman, I. Pirwani and S. Pemmaraju, Oriented edge colorings and link scheduling in sensor networks, in: SENSORWARE 2006: 1st International Workshop on Software for Sensor Networks, 2006.

[009] [10] W. Imrich and S. Klavžar, Product Graphs : Structure and Recognition (John Wiley & Sons, Inc., 2000).

[010] [11] 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 | Zbl 0873.05044

[011] [12] T.H. Marshall, Homomorphism bounds for oriented planar graphs, J. Graph Theory 55 (2007) 175-190, doi: 10.1002/jgt.20233. | Zbl 1120.05039

[012] [13] J. Nesetril, A. Raspaud and É. Sopena, Colorings and girth of oriented planar graphs, Discrete Math. 165-166 (1997) 519-530. | Zbl 0873.05042

[013] [14] P. Ochem, Oriented colorings of triangle-free planar graphs, Information Processing Letters 92 (2004) 71-76, doi: 10.1016/j.ipl.2004.06.012. | Zbl 1173.68593

[014] [15] A. Pinlou and É. Sopena, Oriented vertex and arc colorings of outerplanar graphs, Information Processing Letters 100 (2006) 97-104, doi: 10.1016/j.ipl.2006.06.012. | Zbl 1185.05064

[015] [16] A. Raspaud and É. Sopena, Good and semi-strong colorings of oriented planar graphs, Information Processing Letters 51 (1994) 171-174, doi: 10.1016/0020-0190(94)00088-3. | Zbl 0806.05031

[016] [17] É. Sopena, The chromatic number of oriented graphs, J. Graph Theory 25 (1997) 191-205, doi: 10.1002/(SICI)1097-0118(199707)25:3<191::AID-JGT3>3.0.CO;2-G | Zbl 0874.05026

[017] [18] É. Sopena, Oriented graph coloring, Discrete Math. 229 (2001) 359-369, doi: 10.1016/S0012-365X(00)00216-8. | Zbl 0971.05039