Geodesic
Analogues of cliques for oriented coloring
Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 3, pp. 373-387

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: graph coloring, oriented coloring, clique, planar graph 
@article{DMGT_2004_24_3_a1,
     author = {Klostermeyer, William and MacGillivray, Gary},
     title = {Analogues of cliques for oriented coloring},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {373--387},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2004_24_3_a1/}
}
TY  - JOUR
AU  - Klostermeyer, William
AU  - MacGillivray, Gary
TI  - Analogues of cliques for oriented coloring
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2004
SP  - 373
EP  - 387
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2004_24_3_a1/
LA  - en
ID  - DMGT_2004_24_3_a1
ER  - 
%0 Journal Article
%A Klostermeyer, William
%A MacGillivray, Gary
%T Analogues of cliques for oriented coloring
%J Discussiones Mathematicae. Graph Theory
%D 2004
%P 373-387
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2004_24_3_a1/
%G en
%F DMGT_2004_24_3_a1
Klostermeyer, William; MacGillivray, Gary. Analogues of cliques for oriented coloring. Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 3, pp. 373-387. http://geodesic.mathdoc.fr/item/DMGT_2004_24_3_a1/