Gallai colorings and domination in multipartite digraphs |
| |
| Authors: | András Gyárfás Gábor Simonyi Ágnes Tóth |
| |
| Institution: | 1. Computer and Automation Research Institute, Hungarian Academy of Sciences, , 1518 Budapest, P. O. Box 63 Hungary;2. Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, , 1364 Budapest, P. O. BOX 127 Hungary;3. Department of Computer Science and Information Theory, Budapest University of Technology and Economics, , 1521 Budapest, P. O. Box 91 Hungary |
| |
| Abstract: | Assume that D is a digraph without cyclic triangles and its vertices are partitioned into classes A1, …, At of independent vertices. A set  is called a dominating set of size |S| if for any vertex  there is a w∈U such that (w, v)∈E(D). Let β(D) be the cardinality of the largest independent set of D whose vertices are from different partite classes of D. Our main result says that there exists a h = h(β(D)) such that D has a dominating set of size at most h. This result is applied to settle a problem related to generalized Gallai colorings, edge colorings of graphs without 3‐colored triangles. © 2011 Wiley Periodicals, Inc. J Graph Theory |
| |
| Keywords: | |
|
|
