Analogues of cliques for oriented coloring
William F. Klostermeyer ; Gary MacGillivray
Discussiones Mathematicae Graph Theory, Tome 24 (2004), p. 373-387 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.

Publié le : 2004-01-01
EUDML-ID : urn:eudml:doc:270417 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1237,
     author = {William F. Klostermeyer and Gary MacGillivray},
     title = {Analogues of cliques for oriented coloring},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {24},
     year = {2004},
     pages = {373-387},
     zbl = {1063.05044},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1237}
}

William F. Klostermeyer; Gary MacGillivray. Analogues of cliques for oriented coloring. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 373-387. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1237/

[000] [1] P. Hell and K. Seyffarth, Largest planar graphs of diameter two and fixed maximum degree, Discrete Math. 111 (1993) 313-322, doi: 10.1016/0012-365X(93)90166-Q. | Zbl 0837.05074

[001] [2] A. 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 | Zbl 0873.05044

[002] [3] J. Nesetril, A. Raspaud, and E. Sopena, Colorings and girth of oriented planar graphs, Discrete Math. 165/166 (1997) 519-530, doi: 10.1016/S0012-365X(96)00198-7. | Zbl 0873.05042

[003] [4] A. Raspaud and E. Sopena, Good and semi-strong colorings of oriented planar graphs, Info. Proc. Letters 51 (1994) 171-174, doi: 10.1016/0020-0190(94)00088-3. | Zbl 0806.05031

[004] [5] K. Seyffarth, Maximal planar graphs of diameter two, J. Graph Theory 13 (1989) 619-648, doi: 10.1002/jgt.3190130512. | Zbl 0702.05048

[005] [6] 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 | Zbl 0874.05026

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

[007] [8] E. Sopena, There exist oriented planar graphs with oriented chromatic number at least sixteen, Info. Proc. Letters 81 (2002) 309-312, doi: 10.1016/S0020-0190(01)00246-0.

[008] [9] D. West, Introduction to Graph Theory (Prentice Hall, Upper Saddle River, NJ, 2001) (2nd edition).