Transitive coloring of graphs (Q6573772)

Let \(G\) be a simple graph with vertex set \(V(G)\). A coloring of \(G\) with \(k\) colors is a partition of \(V(G)\) into \(k\) sets. \textit{M. O. Albertson} and \textit{K. L. Collins} [Electron. J. Comb. 3, No. 1, 259--275 (1996; Zbl 0851.05088)] introduced the concept of distinguishing coloring of \(G\), that is a coloring such that no non-trivial automorphism of \(G\) preserves its colors. The distinguishing number \(D(G)\) of \(G\) is the smallest number \(k\) for which a distinguishing \(k\)-coloring of \(G\) exists.\N\NIn this paper, the authors introduce the notion of transitive coloring. Let \(\mathcal V =\{V_1,\dots,V_k\}\) be a \(k\)-coloring of \(G\). An automorphism \(f\) of \(G\) is a transitive color automorphism associate to \(\mathcal V\) if there exist vertices \(v_i\in V_i\) and \(v_j\in V_j\), with \(1\le i\), \(j\le k\), such that (i) \(f(v_i)=v_j\) and (ii) \(f(V_l)=V_l\) for every color class \(V_l\), with \(l\ne i,j\). Such an automorphism is denoted by \(f_{i,j}\). A \(k\)-coloring of \(G\) is called a transitive \(k\)-coloring if for every two distinct colors \(i\) and \(j\), with \(1\le i\), \(j\le k\), there exists a transitive color automorphism \(f_{i,j}\). The largest \(k\) for which there exists a transitive \(k\)-coloring is called the transitive coloring number of \(G\) and denoted by \(\mathcal T(G)\).\N\NIn this paper, the authors study some properties of transitive \(k\)-colorings, determine the transitive coloring number of a few graphs, and study the connection between distinguishing colorings and transitive colorings of graphs.