Upper bounds on the average number of colors in the non-equivalent colorings of a graph

Abstract: A coloring of a graph is an assignment of colors to its vertices such that adjacent vertices have different colors. Two colorings are equivalent if they induce the same partition of the vertex set into color classes. Let

m a t h c a l A (G)

be the average number of colors in the non-equivalent colorings of a graph

G

. We give a general upper bound on

m a t h c a l A (G)

that is valid for all graphs

G

and a more precise one for graphs

G

of order

n

and maximum degree

D e l t a (G) i n 1, 2, n - 2

.

Review text

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)\).

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Upper bounds on the average number of colors in the non-equivalent colorings of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6045131)