Upper bounds on the average number of colors in the non-equivalent colorings of a graph (Q6045131): Difference between revisions

A \(k\)-coloring of a graph \(G\) is a mapping \(c:V(G) \to \{1,2,\ldots ,k\}\) such that \(c(u)\neq c(v)\) for any pair of adjacent vertices \(u\) and \(v\). Two colorings are equivalent if they induce the same partition of \(V(G)\) into color classes. In the paper, the following notations are used. \(S(G,k)\) is the number of non-equivalent \(k\)-colorings of \(G\) and \({\mathcal{B}}(G)=\sum_{k=\chi(G)}^n S(G,n)\) is the total number of non-equivalent colorings of \(G\). Moreover \({\mathcal{T}}(G)=\sum_{k=\chi(G)}^n kS(n,k)\) is the total number of color classes in all non-equivalent colorings of \(G\) and \({\mathcal{A}}(G)=\frac{{\mathcal{T}}(G)}{{\mathcal{B}}(G)}\) is the average number of colors in the non-equivalent colorings of \(G\). The authors of the paper study the upper bounds of \({\mathcal{A}}(G)\) in terms of the order \(n\) of a graph \(G\). They show trivial upper bound \({\mathcal{A}}(G) \leq n\) and \(K_n\) is the only graph achieving the bound. For graphs with maximum degree \(\Delta(G) \in \{1,2,n-2\}\) better upper bounds are presented. For graphs with \(\Delta(G)=n-2\) they prove that \({\mathcal{A}}(G) \leq \frac{n^2-n+1}{n}\), where the equality holds just for a graph \(G\) isomorphic to \(K_{n-1} \cup K_1.\) For graphs with \(\Delta(G) \in \{1,2\}\) they present a graph \(H\) of order \(n\) with the largest \({\mathcal{A}}(G)\) between all graphs of order \(n\) and thus bound average number of colors in the non-equivalent colorings of arbitrary graph with given maximum degree not with the exact function of \(n\) but with \({\mathcal{A}}(H)\). For graphs \(G\) with \(\Delta(G)=1\) it is proved that \({\mathcal{A}}(G) \leq {\mathcal{A}}(\lfloor \frac{n}{2} \rfloor K_2 \cup (n \bmod 2)K_1)\) and that graphs \(\lfloor \frac{n}{2} \rfloor K_2 \cup (n \bmod 2)K_1\) are the only graphs achieving this bound. Finally, for graphs \(G\) with \(\Delta(G)=2\), the authors prove the average number of colors in non-equivalent colorings of a graph \(G\) of order \(n\) is bounded above by \({\mathcal{A}}(U_n)\), where \(n \geq 3\) and \(U_n=\frac{n-1}{3}K_3 \cup K_1\), if \(n \in \{4,7\}\), else \(U_n=\frac{n}{3}K_3\) if rem\((n,3)=0\), \(n \geq 3\), else if rem\((n,3)\in \{1,2\}\), then \(U_n= \frac{n-3-\textrm{rem}(n,3)}{3}K_3 \cup C_{3+rem(n,3)}\). It is also proved that \(U_n\) is the only graph of order \(n\) for which the average number of colors in the non-equivalent colorings is \({\mathcal{A}}(U_n)\).