PDF
Discussiones Mathematicae Graph Theory 31(4) (2011)
675-686
DOI: https://doi.org/10.7151/dmgt.1572
Oriented colouring of some graph products
N.R. Aravind
The Institute of Mathematical Sciences | N. Narayanan
C R RAO Advanced Institute for Mathematics | C.R. Subramanian
The Institute of Mathematical Sciences |
Abstract
We obtain some improved upper and lower bounds on the oriented chromatic number for different classes of products of graphs.Keywords: oriented colouring
2010 Mathematics Subject Classification: 05C15, 05C20.
References
[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. |
[2] | O.V. Borodin, A.V. Kostochka, J. Nesetril, A. Raspaud and E. 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. |
[3] | O.V. Borodin, A.V. Kostochka, A. Raspaud and E. Sopena. Acyclic colouring of 1-planar graphs, Discrete Appl. Math. 114 (2001) 29--41, doi: 10.1016/S0166-218X(00)00359-0. |
[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. |
[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. |
[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. |
[7] | E. Fried, On homogeneous tournaments, Combinatorial Theory and its Applications 2 (1970) 467--476. |
[8] | P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications (28), 2004. |
[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, E. 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. |
[12] | T.H. Marshall, Homomorphism bounds for oriented planar graphs, J. Graph Theory 55 (2007) 175--190, doi: 10.1002/jgt.20233. |
[13] | J. Nesetril, A. Raspaud and E. Sopena, Colorings and girth of oriented planar graphs, Discrete Math. 165--166 (1997) 519--530. |
[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. |
[15] | A. Pinlou and E. Sopena, Oriented vertex and arc colorings of outerplanar graphs, Information Processing Letters 100 (2006) 97--104, doi: 10.1016/j.ipl.2006.06.012 . |
[16] | A. Raspaud and E. 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. |
[17] | E. 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. |
[18] | E. Sopena, Oriented graph coloring, Discrete Math. 229 (2001) 359--369, doi: 10.1016/S0012-365X(00)00216-8. |
Received 5 March 2010
Revised 11 October 2010
Accepted 11 October 2010
Close