Generalization of transitive fraternal augmentations for directed graphs and its applications

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 , 1. , y ) ∈ E ( G → ) and ( x , z ) ∈ E ( G → ) then ( y , z ) ∈ E ( H → ) or ( z , y ) ∈ E ( H → ) (fraternity); , y ) ∈ E ( G → ) and ( y , z ) ∈ E ( G → ) then ( x , z ) ∈ E ( H → ) (transitivity). is 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 col 2 ( 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 col k + 1 ( G ) with a function f ( ∇ k ( G ) ) . On the other hand, ∇ k ( G ) ≤ ( col 2 k + 1 ( G ) ) 2 k + 1 . We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs.