Geodesic
Generalized colorings and avoidable orientations
Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 1, pp. 137-145

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

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.
Keywords: hereditary property, graph coloring 
@article{DMGT_1997_17_1_a10,
     author = {Szigeti, Jen\H{o} and Tuza, Zsolt},
     title = {Generalized colorings and avoidable orientations},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {137--145},
     publisher = {mathdoc},
     volume = {17},
     number = {1},
     year = {1997},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a10/}
}
TY  - JOUR
AU  - Szigeti, Jenő
AU  - Tuza, Zsolt
TI  - Generalized colorings and avoidable orientations
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1997
SP  - 137
EP  - 145
VL  - 17
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a10/
LA  - en
ID  - DMGT_1997_17_1_a10
ER  - 
%0 Journal Article
%A Szigeti, Jenő
%A Tuza, Zsolt
%T Generalized colorings and avoidable orientations
%J Discussiones Mathematicae. Graph Theory
%D 1997
%P 137-145
%V 17
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a10/
%G en
%F DMGT_1997_17_1_a10
Szigeti, Jenő; Tuza, Zsolt. Generalized colorings and avoidable orientations. Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 1, pp. 137-145. http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a10/