PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2004 | 24 | 3 | 373-387
Tytuł artykułu

Analogues of cliques for oriented coloring

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
24
Numer
3
Strony
373-387
Opis fizyczny
Daty
wydano
2004
otrzymano
2002-10-15
poprawiono
2004-03-11
Twórcy
  • Department of Computer and Information Sciences, University of North Florida, Jacksonville, FL 32224-2669, U.S.A.
  • Department of Mathematics and Statistics, University of Victoria, Victoria, Canada
Bibliografia
  • [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.
  • [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
  • [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.
  • [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.
  • [5] K. Seyffarth, Maximal planar graphs of diameter two, J. Graph Theory 13 (1989) 619-648, doi: 10.1002/jgt.3190130512.
  • [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
  • [7] E. Sopena, Oriented graph coloring, Discrete Math. 229 (2001) 359-369, doi: 10.1016/S0012-365X(00)00216-8.
  • [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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1237
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.