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

Abstract

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

How to cite

top

N.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. [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. [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. [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. [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. [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. [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. [7] E. Fried, On homogeneous tournaments, Combinatorial Theory and its Applications 2 (1970) 467-476. Zbl0215.33704
  8. [8] P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications (28), 2004. Zbl1062.05139
  9. [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. [10] W. Imrich and S. Klavžar, Product Graphs : Structure and Recognition (John Wiley & Sons, Inc., 2000). 
  11. [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. [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. [13] J. Nesetril, A. Raspaud and É. Sopena, Colorings and girth of oriented planar graphs, Discrete Math. 165-166 (1997) 519-530. Zbl0873.05042
  14. [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. [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. [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. [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. [18] É. Sopena, Oriented graph coloring, Discrete Math. 229 (2001) 359-369, doi: 10.1016/S0012-365X(00)00216-8. Zbl0971.05039

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.