Generalization of transitive fraternal augmentations for directed graphs and its applications
Generalization of transitive fraternal augmentations for directed graphs and its applications
复制标题
有向图传递兄弟增广的推广及其应用
DOI：
10.1016/j.disc.2009.02.028
复制
发表时间：
2009-07
影响因子：
0.8
通讯作者：
Yang, Daqing
中科院分区：
文献类型：
--
作者：
Yang, Daqing
Let G→ be a directed graph. A transitive fraternal augmentation of G→ is a directed graph H→ with the same vertex set, including all the arcs of G→ and such that for any vertices x,y,z, In this paper, we explore some generalization of the transitive fraternal augmentations for directed graphs and its applications. In particular, we show that the 2-coloring number col2(G)≤O(∇1(G)∇0(G)2), where ∇k(G) (k≥0) denotes the greatest reduced average density with depth k of a graph G; we give a constructive proof that ∇k(G) bounds the distance (k+1)-coloring number colk+1(G) with a function f(∇k(G)). On the other hand, [Formula: see text] . We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs.
登录
查看更多内容
DOI：
10.1006/jctb.1998.1878
发表时间：
1999-03
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Xuding Zhu
通讯作者：
Xuding Zhu
影响因子：
0.9
作者：
O. Borodin;A. Kostochka;N. Sheikh;Gexin Yu
通讯作者：
O. Borodin;A. Kostochka;N. Sheikh;Gexin Yu
DOI：
10.1016/j.ejc.2009.03.012
发表时间：
2009-10
期刊：
Eur. J. Comb.
影响因子：
--
作者：
J. Nesetril;P. D. Mendez
通讯作者：
J. Nesetril;P. D. Mendez
DOI：
10.1016/j.disc.2008.03.024
发表时间：
2009-09
期刊：
Discret. Math.
影响因子：
--
作者：
Xuding Zhu
通讯作者：
Xuding Zhu
影响因子：
1
作者：
N. Alon;J. Grytczuk;Mariusz Haluszczak;O. Riordan
通讯作者：
N. Alon;J. Grytczuk;Mariusz Haluszczak;O. Riordan