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,zx,y,z, 1.if (x,y)∈E(G→) and (x,z)∈E(G→) then (y,z)∈E(H→) or (z,y)∈E(H→) (fraternity);2.if (x,y)∈E(G→) and (y,z)∈E(G→) then (x,z)∈E(H→) (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)col2(G)≤O(∇1(G)∇0(G)2), where ∇k(G)∇k(G) (k≥0k≥0) denotes the greatest reduced average density with depth kk of a graph GG; we give a constructive proof that ∇k(G)∇k(G) bounds the distance (k+1)(k+1)-coloring number colk+1(G)colk+1(G) with a function f(∇k(G))f(∇k(G)). On the other hand, ∇k(G)≤(col2k+1(G))2k+1∇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.