Gallai colorings and domination in multipartite digraphs
Gallai colorings and domination in multipartite digraphs
复制标题
加莱着色和多部分有向图中的支配
DOI：
10.1002/jgt.20646
复制
发表时间：
2010
影响因子：
0.9
通讯作者：
Á. Tóth
中科院分区：
文献类型：
--
作者：
A. Gyárfás;G. Simonyi;Á. Tóth
假设D是一个没有循环三角形的有向图，它的顶点被划分为独立顶点的A1，…，At类。如果对于任意顶点存在w∈U使得(w, v)∈E(D)，则称为规模为|S|的支配集。设β(D)是顶点来自D的不同部类的D的最大独立集的基性。我们的主要结果表明，存在h = h（β(D)）使得D有一个最大为h的支配集。这个结果应用于解决一个与广义Gallai着色有关的问题，无3色三角形图的边着色。©2011 Wiley期刊公司J图论
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
DOI：
--
发表时间：
1984
期刊：
--
影响因子：
--
作者：
M. Wodzicki
通讯作者：
M. Wodzicki