ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2018-2019): c. 84%
Discussiones Mathematicae Graph Theory 17(1) (1997)
Mathematical Institute, University of Miskolc
H-3515 Miskolc-Egyetemváros, Hungary
Computer and Automation Institute
Hungarian Academy of Sciences
H-1111 Budapest, Kende u. 13-17, Hungary
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.
1991 Mathematics Subject Classification: 05C15, 05C75.