Generalization of transitive fraternal augmentations for directed graphs and its applications |
| |
Authors: | Daqing Yang |
| |
Institution: | Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian 350002, China |
| |
Abstract: | Let be a directed graph. A transitive fraternal augmentation of is a directed graph with the same vertex set, including all the arcs of and such that for any vertices x,y,z, - 1.
- if and then or (fraternity);
- 2.
- if and then (transitivity).
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, ∇k(G)≤(col2k+1(G))2k+1. We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs. |
| |
Keywords: | Directed graph Transitive fraternal augmentation Generalized coloring number Greatest reduced average density Nonrepetitive coloring |
本文献已被 ScienceDirect 等数据库收录! |
|