PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1997 | 17 | 1 | 137-145
Tytuł artykułu

Generalized colorings and avoidable orientations

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed graphs.
Słowa kluczowe
Wydawca
Rocznik
Tom
17
Numer
1
Strony
137-145
Opis fizyczny
Daty
wydano
1997
otrzymano
1997-01-14
Twórcy
  • Mathematical Institute, University of Miskolc, H-3515 Miskolc-Egyetemváros, Hungary
autor
  • Computer and Automation Institute, Hungarian Academy of Sciences, H-1111 Budapest, Kende u. 13-17, Hungary
Bibliografia
  • [1] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discussiones Mathematicae Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
  • [2] J. Bucko, M. Frick, P. Mihók and R. Vasky, Uniquely partitionable graphs, Discussiones Mathematicae Graph Theory 17 (1997) 103-113, doi: 10.7151/dmgt.1043.
  • [3] Y. Caro, Private communication, 1989.
  • [4] T. Gallai, On directed paths and circuits, in: P. Erd os and G.O.H. Katona, eds., Theory of Graphs, Proc. Colloq. Math. Soc. János Bolyai, Tihany (Hungary) 1966 (Academic Press, San Diego, 1968) 115-118.
  • [5] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58.
  • [6] G.J. Minty, A theorem on n-colouring the points of a linear graph, Amer. Math. Monthly 67 (1962) 623-624, doi: 10.2307/2310826.
  • [7] R. Roy, Nombre chromatique et plus longs chemins d'un graphe, Revue AFIRO 1 (1967) 127-132.
  • [8] Zs. Tuza, Graph coloring in linear time, J. Combin. Theory (B) 55 (1992) 236-243, doi: 10.1016/0095-8956(92)90042-V.
  • [9] Zs. Tuza, Chromatic numbers and orientations, Unpublished manuscript, February 1993.
  • [10] Zs. Tuza, Some remarks on the Gallai-Roy Theorem, in preparation.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1047
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ć.