Oriented colouring of some graph products

• Autorzy: N.R. Aravind , N. Narayanan , C.R. Subramanian
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

oriented colouring

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C20: Directed graphs (digraphs), tournaments

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2011
• Tom: 31
• Numer: 4
• Strony: 675-686

Daty

wydano

2011

otrzymano

2010-03-05

poprawiono

2010-10-11

zaakceptowano

2010-10-11

Twórcy

autor

N.R. Aravind

• The Institute of Mathematical Sciences, Taramani, Chennai, India

autor

N. Narayanan

• C R RAO Advanced Institute for Mathematics, Statistics and Computer Science, University of Hyderabad Campus, Hyderabad, India

autor

C.R. Subramanian

• The Institute of Mathematical Sciences, Taramani, Chennai, India

Bibliografia

• [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 É. 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 É. 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, É. 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 É. 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 É. 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 É. 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] É. 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] É. Sopena, Oriented graph coloring, Discrete Math. 229 (2001) 359-369, doi: 10.1016/S0012-365X(00)00216-8.

Identyfikatory

DOI

10.7151/dmgt.1572