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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1047,
author = {Jen\H o Szigeti and Zsolt Tuza},
title = {Generalized colorings and avoidable orientations},
journal = {Discussiones Mathematicae Graph Theory},
volume = {17},
year = {1997},
pages = {137-145},
zbl = {0908.05039},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1047}
}
Jenő Szigeti; Zsolt Tuza. Generalized colorings and avoidable orientations. Discussiones Mathematicae Graph Theory, Tome 17 (1997) pp. 137-145. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1047/
[000] [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. | Zbl 0902.05026
[001] [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. | Zbl 0906.05057
[002] [3] Y. Caro, Private communication, 1989.
[003] [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.
[004] [5] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58. | Zbl 0623.05043
[005] [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. | Zbl 0108.36601
[006] [7] R. Roy, Nombre chromatique et plus longs chemins d'un graphe, Revue AFIRO 1 (1967) 127-132. | Zbl 0157.31302
[007] [8] Zs. Tuza, Graph coloring in linear time, J. Combin. Theory (B) 55 (1992) 236-243, doi: 10.1016/0095-8956(92)90042-V. | Zbl 0709.05019
[008] [9] Zs. Tuza, Chromatic numbers and orientations, Unpublished manuscript, February 1993.
[009] [10] Zs. Tuza, Some remarks on the Gallai-Roy Theorem, in preparation.