# Oriented colouring of some graph products

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

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 4, page 675-686
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topN.R. Aravind, N. Narayanan, and C.R. Subramanian. "Oriented colouring of some graph products." Discussiones Mathematicae Graph Theory 31.4 (2011): 675-686. <http://eudml.org/doc/270980>.

@article{N2011,

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

author = {N.R. Aravind, N. Narayanan, C.R. Subramanian},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {oriented colouring},

language = {eng},

number = {4},

pages = {675-686},

title = {Oriented colouring of some graph products},

url = {http://eudml.org/doc/270980},

volume = {31},

year = {2011},

}

TY - JOUR

AU - N.R. Aravind

AU - N. Narayanan

AU - C.R. Subramanian

TI - Oriented colouring of some graph products

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 4

SP - 675

EP - 686

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

LA - eng

KW - oriented colouring

UR - http://eudml.org/doc/270980

ER -

## References

top- [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. Zbl1267.05111
- [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. Zbl0932.05033
- [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. Zbl0996.05053
- [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. Zbl0809.03005
- [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. Zbl1185.05059
- [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. Zbl1173.68604
- [7] E. Fried, On homogeneous tournaments, Combinatorial Theory and its Applications 2 (1970) 467-476. Zbl0215.33704
- [8] P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications (28), 2004. Zbl1062.05139
- [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.
- [10] W. Imrich and S. Klavžar, Product Graphs : Structure and Recognition (John Wiley & Sons, Inc., 2000).
- [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 Zbl0873.05044
- [12] T.H. Marshall, Homomorphism bounds for oriented planar graphs, J. Graph Theory 55 (2007) 175-190, doi: 10.1002/jgt.20233. Zbl1120.05039
- [13] J. Nesetril, A. Raspaud and É. Sopena, Colorings and girth of oriented planar graphs, Discrete Math. 165-166 (1997) 519-530. Zbl0873.05042
- [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. Zbl1173.68593
- [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. Zbl1185.05064
- [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. Zbl0806.05031
- [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 Zbl0874.05026
- [18] É. Sopena, Oriented graph coloring, Discrete Math. 229 (2001) 359-369, doi: 10.1016/S0012-365X(00)00216-8. Zbl0971.05039

## Citations in EuDML Documents

top## NotesEmbed ?

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