Analogues of cliques for oriented coloring
William F. Klostermeyer; Gary MacGillivray
Discussiones Mathematicae Graph Theory (2004)
- Volume: 24, Issue: 3, page 373-387
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topWilliam F. Klostermeyer, and Gary MacGillivray. "Analogues of cliques for oriented coloring." Discussiones Mathematicae Graph Theory 24.3 (2004): 373-387. <http://eudml.org/doc/270417>.
@article{WilliamF2004,
abstract = {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.},
author = {William F. Klostermeyer, Gary MacGillivray},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph coloring; oriented coloring; clique; planar graph; colouring; orientation},
language = {eng},
number = {3},
pages = {373-387},
title = {Analogues of cliques for oriented coloring},
url = {http://eudml.org/doc/270417},
volume = {24},
year = {2004},
}
TY - JOUR
AU - William F. Klostermeyer
AU - Gary MacGillivray
TI - Analogues of cliques for oriented coloring
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 3
SP - 373
EP - 387
AB - 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.
LA - eng
KW - graph coloring; oriented coloring; clique; planar graph; colouring; orientation
UR - http://eudml.org/doc/270417
ER -
References
top- [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. Zbl0837.05074
- [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 Zbl0873.05044
- [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. Zbl0873.05042
- [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. Zbl0806.05031
- [5] K. Seyffarth, Maximal planar graphs of diameter two, J. Graph Theory 13 (1989) 619-648, doi: 10.1002/jgt.3190130512. Zbl0702.05048
- [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 Zbl0874.05026
- [7] E. Sopena, Oriented graph coloring, Discrete Math. 229 (2001) 359-369, doi: 10.1016/S0012-365X(00)00216-8. Zbl0971.05039
- [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.
- [9] D. West, Introduction to Graph Theory (Prentice Hall, Upper Saddle River, NJ, 2001) (2nd edition).
NotesEmbed ?
topYou 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.