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 \({\mathcal {A}}(G)\) be the average number of colors in the non-equivalent colorings of a graph G. We give a general upper bound on \({\mathcal {A}}(G)\) that is valid for all graphs G and a more precise one for graphs G of order n and maximum degree \(\Delta (G)\in \{1,2,n-2\}\).
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
A coloring of a graph G is an assignment of colors to its vertices such that adjacent vertices have different colors. The total number \({{\mathcal {B}}}(G)\) of non-equivalent colorings (i.e., with different partitions into color classes) of a graph G is the number of partitions of the vertex set of G whose blocks are stable sets (i.e., sets of pairwise non-adjacent vertices). This invariant has been studied by several authors in the last few years [1, 5,6,7, 9, 11] under the name of (graphical) Bell number. It is related to the standard Bell number \({\textsf {B}}_{n}\) (sequence A000110 in OEIS [13]) that corresponds to the number of partitions of a set of n elements into non-empty subsets, and is thus obviously the same as the number of non-equivalent colorings of the empty graph or order n (i.e., the graph with n vertices and without any edge).
The 2-Bell number \({\textsf {T}}_{n}\) (sequence A005493 in OEIS [13]) is the total number of blocks in all partitions of a set of n elements. Odlyzko and Richmond [12] have studied the average number \(\textsf{A}_{n}\) of blocks in a partition of a set of n elements, which can be defined as \({\textsf {A}}_{n}=\frac{{\textsf {T}}_{n}}{{\textsf {B}}_{n}}.\) The corresponding concept in graph theory is the average number \({\mathcal {A}}(G)\) of colors in the non-equivalent colorings of a graph G. This graph invariant was recently defined in [8]. When constraints (represented by edges in G) impose that certain pairs of elements (represented by vertices) cannot belong to the same block of a partition, \({\mathcal {A}}(G)\) is the average number of blocks in the partitions that respect all constraints. Clearly, \({\mathcal {A}}(G)={\textsf {A}}_{n}\) if G is the empty graph of order n.
Lower bounds on \({\mathcal {A}}(G)\) are studied in [10]. The authors mention that there is no known lower bound on \({\mathcal {A}}(G)\) which is a function of n and such that there exists at least one graph of order n which reaches it. As we will show, the situation is not the same for the upper bound. Indeed, we show that there is an upper bound on \({\mathcal {A}}(G)\) which is a function of n and such that there exists exactly one graph of order n which reaches it. We also give a sharper upper bound for graphs with maximum degree \(\Delta (G)\in \{1,2,n-2\}\).
In the next section, we fix some notations and summarize our contributions. Section 3 is devoted to properties of \({\mathcal {A}}(G)\) and basic ingredients that we will use in Sect. 4 for proving the validity of the upper bounds on \({\mathcal {A}}(G)\).
2 Notation and Summary of Contributions
For basic notions of graph theory that are not defined here, we refer to Diestel [3]. The order of a graph \(G=(V,E)\) is its number |V| of vertices, and the size of G is its number |E| of edges. We write \({\overline{G}}\) for the complement of G and \(G \simeq H\) if G and H are two isomorphic graphs. We denote by \({\textsf {K}}_{n}\) (resp. \({\textsf {C}}_{n}\), \({\textsf {P}}_{n}\) and \(\overline{{\textsf {K}}}_{n}\)) the complete graph (resp. the cycle, the path and the empty graph) of order n. For a subset W of vertices in G, we write G[W] for the subgraph induced by W. Given two graphs \(G_1\) and \(G_2\) (with disjoint sets of vertices), we write \(G_1\cup G_2\) for the disjoint union of \(G_1\) and \(G_2\), and pG is the disjoint union of p copies of G.
Let N(v) be the set of vertices adjacent to a vertex v in G. We say that v is isolated if \(|N(v)| = 0\). We write \(\Delta (G)\) for the maximum degree of G. A vertex v of a graph G is simplicial if the induced subgraph G[N(v)] of G is a clique. Given two vertices u and v in a graph G, we use the following notations:
-
\(G_{\mid uv}\) is the graph obtained by identifying (merging) the vertices u and v and, if \(uv \in E(G)\), by removing the edge uv;
-
if \(uv \in E(G)\), \(G - uv\) is the graph obtained by removing the edge uv from G;
-
if \(uv \notin E(G)\), \(G + uv\) is the graph obtained by adding the edge uv in G;
-
\(G - v\) is the graph obtained from G by removing v and all its incident edges.
A coloring of a graph G is an assignment of colors to the vertices of G such that adjacent vertices have different colors. The chromatic number \(\chi \)(G) is the minimum number of colors in a coloring of G. Two colorings are equivalent if they induce the same partition of the vertex set into color classes. Let \(S(G,k)\) be the number of non-equivalent colorings of a graph G that use exactly k colors. Then, the total number \({{\mathcal {B}}}(G)\) of non-equivalent colorings of a graph G is defined by
and the total number \({{\mathcal {T}}}(G)\) of color classes in the non-equivalent colorings of a graph G is defined by
In this paper, we study the average number \({\mathcal {A}}(G)\) of colors in the non-equivalent colorings of a graph G, that is,
For illustration, as shown in Fig. 1, there are one non-equivalent coloring of \(\textsf{P}_{4}\) with 2 colors, three with 3 colors, and one with 4 colors, which gives \({{\mathcal {B}}}({\textsf {P}}_{4})=5\), \({{\mathcal {T}}}({\textsf {P}}_{4})=15\) and \({\mathcal {A}}({\textsf {P}}_{4})=\frac{15}{5}=3.\)
The aim of this paper is to determine a general upper bound on \({\mathcal {A}}(G)\) that is valid for all graphs G and a sharper one for graphs G of order n and maximum degree \(\Delta (G)\in \{1,2,n-2\}\). More precisely, given a graph G of order n, we show that
-
\({\mathcal {A}}(G) \le n\), with equality if and only if \(G \simeq {\textsf {K}}_{n}\);
-
if \(\Delta (G)=n-2\) then \({\mathcal {A}}(G) \le \frac{n^2 - n + 1}{n}\), with equality if and only if \(G\simeq {\textsf {K}}_{n-1} \cup {\textsf {K}}_{1}\);
-
if \(\Delta (G)=1\) then \({\mathcal {A}}(G) \le {\mathcal {A}}({\lfloor }{\frac{n}{2}}{\rfloor } {\textsf {K}}_{2}\cup (n\bmod 2){\textsf {K}}_{1}) \), with equality if and only if \(G\simeq {\lfloor }{\frac{n}{2}}{\rfloor } {\textsf {K}_{2}}\cup (n\bmod 2){\textsf {K}}_{1}\);
-
if \(\Delta (G)=2\) then \({\mathcal {A}} (G) \le {\mathcal {A}}({{\textsf {U}}_{n}})\), with equality if and only if \(G \simeq {{\textsf {U}}_{n}}\), where
$$\begin{aligned} \begin{aligned} {{\textsf {U}}_{n}} = {\left\{ \begin{array}{ll} \frac{n}{3} {\textsf {K}}_{3} &{}{} \text{ if } n\ {\text{ mod } \ }3 = 0, \text{ and } n \ge 3,\\ \frac{n-1}{3}{\textsf {K}}_{3} \cup {\textsf {K}}_{1} &{}{} \text{ if } n = 4 \text{ or } n = 7,\\ \frac{n-4}{3} {\textsf {K}}_{3} \cup {\textsf {C}}_{4} &{}{} \text{ if } n\ {\text{ mod } \ }3 = 1, \text{ and } n \ge 10,\\ \frac{n-5}{3} {\textsf {K}}_{3} \cup {\textsf {C}_{5}} &{}{} \text{ if } n\ {\text{ mod } \ }3 = 2, \text{ and } n \ge 5. \end{array}\right. } \end{aligned} \end{aligned}$$
3 Properties of \(S(G,k)\) and \({\mathcal {A}}(G)\)
As for several other invariants in graph coloring, the deletion-contraction rule (also often called the Fundamental Reduction Theorem [4]) can be used to compute \({{\mathcal {B}}}(G)\) and \({{\mathcal {T}}}(G)\). More precisely, let u and v be any pair of distinct vertices of G. As shown in [6, 11], we have
It follows that
Many properties on \({\mathcal {A}}(G)\) are proved in [8] and [10]. We mention here some of them that will be useful for proving the validity of the upper bounds on \({\mathcal {A}}(G)\) given in Sect. 4.
Proposition 1
([10]) Let v be a simplicial vertex in a graph G. Then \({\mathcal {A}}(G) > {\mathcal {A}}(G-v)\).
Proposition 2
( [10]) Let v be a simplicial vertex of degree at least one in a graph G, and let w be one of its neighbors in G. Then \({\mathcal {A}}(G)>{\mathcal {A}}(G-vw)\).
Proposition 3
( [10]) \({\mathcal {A}}(G\cup {\textsf {C}}_{n})>{\mathcal {A}}(G\cup {\textsf {P}}_{n})\) for all \(n\ge 3\) and all graphs G.
Proposition 4
( [8]) Let G, H and \(F_1,\ldots ,F_r\) be \(r+2\) graphs, and let \(\alpha _1,\ldots ,\alpha _r\) be r positive numbers such that
-
\({{\mathcal {B}}}(G)={{\mathcal {B}}}(H)+\displaystyle \sum _{i=1}^r\alpha _i{{\mathcal {B}}}(F_i)\)
-
\({{\mathcal {T}}}(G)={{\mathcal {T}}}(H)+\displaystyle \sum _{i=1}^r\alpha _i{{\mathcal {T}}}(F_i)\)
-
\({\mathcal {A}}(F_i)<{\mathcal {A}}(H)\) for all \(i=1,\ldots ,r\).
Then \({\mathcal {A}}(G)<{\mathcal {A}}(H)\).
Given two graphs \(H_1\) and \(H_2\), we now give a sufficient condition for \({\mathcal {A}}(G\cup H_1)\) to be strictly larger than \({\mathcal {A}}(G\cup H_2)\) for all graphs G.
Proposition 5
Let \(H_1\) and \(H_2\) be any two graphs such that \(S(H_1,k) S(H_2,k') \ge S(H_2,k)S(H_1,k')\) for all \(k {>} k'\), the inequality being strict for at least one pair \((k,k')\). Then \({{\mathcal {A}}(G\cup H_1) > {\mathcal {A}}(G\cup H_2)}\) for all graphs G.
Proof
We first prove that \({{\mathcal {B}}}(G \cup H) = \sum _{k=1}^{n} S(H,k) {{\mathcal {B}}}(G \cup {\textsf {K}}_{k})\) for all graphs H of order n. This is clearly true for \(n=1\). For larger values of n we proceed by double induction on the order n and the size m of H.
-
If \(m=\frac{n(n-1)}{2}\), then \(H\simeq {\textsf {K}}_{n}\). Since \(S({\textsf {K}}_{n},i)=0\) for \(i=1,\ldots ,n-1\) and \(S({\textsf {K}}_{n},n)=1\), we have \({{\mathcal {B}}}(G \cup {\textsf {K}}_{n}) = \sum _{k=1}^{n} S({\textsf {K}}_{n},k) {{\mathcal {B}}}(G \cup {\textsf {K}}_{n})\).
-
If \(m<\frac{n(n-1)}{2}\), then H contains two non-adjacent vertices u and v and we know from Eq. (4) that \({{\mathcal {B}}}(G \cup H)={{\mathcal {B}}}(G\cup (H + uv)) + {{\mathcal {B}}}(G\cup H_{\mid uv})\). Since \(H + uv\) has order n and size \(m+1\) and \(H_{\mid uv}\) has order \(n-1\), we know by induction that
$$\begin{aligned} \begin{aligned} {{\mathcal {B}}}(G \cup H)&=\sum _{k=1}^{n} S(H + uv,k) {{\mathcal {B}}}(G \cup {\textsf {K}}_{k}) + \sum _{k=1}^{n-1} S(H_{\mid uv},k) {{\mathcal {B}}}(G \cup {\textsf {K}}_{k})\\ {}&=\sum _{k=1}^{n} \bigl (S(H + uv,k) +S(H_{\mid uv},k)\bigr ) {{\mathcal {B}}}(G \cup {\textsf {K}}_{k})\\ {}&=\sum _{k=1}^{n} S(H,k) {{\mathcal {B}}}(G \cup {\textsf {K}}_{k}). \end{aligned} \end{aligned}$$
A similar proof shows that \({{\mathcal {T}}}(G \cup H) = \sum _{k=1}^{n} S(H,k) {{\mathcal {T}}}(G \cup {\textsf {K}}_{k})\) for all graphs H of order n. Now let \(f(k,k')=S(H_1,k) S(H_2,k') - S(H_2,k)S(H_1,k')\) and assume that \(H_1\) and \(H_2\) are of order \(n_1\) and \(n_2\), respectively. Note that \(n_1\ge n_2\) else we would have \(n_2>n_1\) and \(f(n_2,n_1)=S(H_1,n_2) S(H_2,n_1) - S(H_2,n_2)S(H_1,n_1)=-1<0\). Now,
Since \(f(k,k)=0\) for all k and \(f(k,k')=-f(k',k)\) for all \(k\ne k'\), we deduce
Note that if \(k>k'\), then \(G\cup {\textsf {K}}_{k}\) is obtained from \(G\cup {\textsf {K}}_{k'}\) by repeatedly adding a simplicial vertex. Hence, we know from Proposition 1 that
Since \(f(k,k')=S(H_1,k)S(H_2,k')-S(H_1,k')S(H_2,k)\) is positive for all \(k>k'\), and strictly positive for at least one such pair, we have \({\mathcal {A}}(G\cup H_1) - {\mathcal {A}}(G\cup H_2)> 0\). \(\square \)
Some graphs G of order \(n\le 9\) will play a special role in the next section. The values \(S(G,k)\) of these graphs, with \(2\le k\le n\), are given in Table 1. These values lead to the following lemma.
Lemma 6
The following strict inequalities are valid for all graphs G:
Proof
All these inequalities can be obtained from Proposition 5 by using the values given in Table 1. For example, to check that (a) holds, the \(4^{th}\) and \(7^{th}\) lines of Table 1 allow to check that \( S(2\textsf{C}_{3},k)S(\textsf{C}_{6},k')-S(\textsf{C}_{6},k) S(2\textsf{C}_{3},k') \ge 0\) for all \(k > k'\) and at least one of these values is strictly positive. \(\square \)
We now show the validity of four lemmas which will be helpful for proving that \({\mathcal {A}}(G \cup {\textsf{C}}_{n}) < {\mathcal {A}}(G \cup {\textsf{C}}_{n-3} \cup {\textsf{C}}_{3})\) for all \(n\ge 6\). A direct consequence of this result will be that a graph G that maximizes \({\mathcal {A}}(G)\) among the graphs with maximum degree 2 cannot contain an induced \({\textsf{C}}_{n} \) with \(n\ge 6\).
Lemma 7
\(S({\textsf{C}}_{n},k) = (k-1)S({\textsf{C}}_{n-1},k)+S({\textsf{C}}_{n-1},k-1) \) for all \(n \ge 4\) and all \(k \ge 3\).
Proof
The values in the following table show that the result is true for \(n=4\).
k | 2 | 3 | 4 |
---|---|---|---|
\(S({\textsf {C}}_{4},k)\) | 1 | 2 | 1 |
\(S({\textsf {C}}_{3},k)\) | 0 | 1 | 0 |
For larger values of n, we proceed by induction. So assume \(n\ge 5\), let u be a vertex in \({\textsf{C}}_{n} \), and let v and w be its two neighbors in \({\textsf{C}}_{n} \). Let us analyze the set of non-equivalent colorings of \({\textsf{C}}_{n} \) that use exactly k colors:
-
There are \((k-1)S({\textsf{C}}_{n-2},k)\) such colorings where v and w have the same color and at least one vertex of \({\textsf{C}}_{n}-u\) has the same color as u;
-
There are \(S({\textsf{C}}_{n-2},k-1)\) such colorings where v and w have the same color and no vertex on \({\textsf{C}}_{n}-u\) has the same color as u;
-
There are \((k-2)S({\textsf{C}}_{n-1},k) \) such colorings where v and w have different colors and at least one vertex of \({\textsf{C}}_{n}-u \) has the same color as u;
-
There are \(S({\textsf{C}}_{n-1},k-1) \) such colorings where v and w have different colors and no vertex on \({\textsf{C}}_{n}-u \) has the same color as u.
Hence,
\(\square \)
Lemma 8
If \(n\ge 7\) and \(k\le n\) then
where
Proof
The values in Table 1 show that the result is true for \(n=7\). For larger values of n, we proceed by induction. Let u be a vertex in \({\textsf{C}}_{n-3} \), and let v and w be its two neighbors. We analyze the set of non-equivalent colorings of \({\textsf{C}}_{n-3} \cup {\textsf{C}}_{3} \) that use exactly k colors:
-
There are \((k-1)S({\textsf{C}}_{n-5} \cup {\textsf{C}}_{3},k) \) such colorings where v and w have the same color and at least one vertex of \({\textsf{C}}_{n-3} \cup {\textsf{C}}_{3}-u \) has the same color as u;
-
There are \(S({\textsf{C}}_{n-5} \cup {\textsf{C}}_{3},k-1) \) such colorings where v and w have the same color and no vertex on \({\textsf{C}}_{n-3} \cup {\textsf{C}}_{3}-u \) has the same color as u;
-
There are \((k-2)S({\textsf{C}}_{n-4} \cup {\textsf{C}}_{3},k) \) such colorings where v and w have different colors and at least one vertex of \({\textsf{C}}_{n-3} \cup {\textsf{C}}_{3}-u \) has the same color as u;
-
There are \(S({\textsf{C}}_{n-4} \cup {\textsf{C}}_{3},k-1) \) such colorings where v and w have different colors and no vertex on \({\textsf{C}}_{n-3} \cup {\textsf {C}}_{3}-u \) has the same color as u.
Hence,
\(\square \)
For \(n\ge 3\), let \({\textsf {Q}}_{n} \) be the graph obtained from \({\textsf {P}}_{n} \) by adding an edge between an extremity v of \({\textsf {P}}_{n} \) and the vertex at distance 2 from v on \({\textsf {P}}_{n} \).
Lemma 9
If \(n\ge 6\) and \(k\le n\) then \(S({\textsf{C}}_{n-3} \cup {\textsf{C}}_{3}, k) = S({\textsf{Q}}_{n},k) - (-1)^n \rho _k \) where
Proof
The values in the following table show that the result is true for \(n=6\).
k | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|
\(S(2{\textsf {C}}_{3},k)\) | 0 | 6 | 18 | 9 | 1 |
\(S({\textsf {Q}}_{6},k)\) | 0 | 8 | 19 | 9 | 1 |
For larger values of n, we proceed by induction. Equations (1) and (2) give
\(\square \)
Lemma 10
The following inequalities are valid for all \(n\ge 9\):
-
(a)
\(S({\textsf{C}}_{n},k)> S({\textsf{C}}_{n},k-1) \) for all \(k\in \{3,4,5\}\);
-
(b)
\(S({\textsf{C}}_{n},k) > 3 S({\textsf{C}}_{n-1},k-1) \) for all \(k \in \{3,4,5,6\}\);
-
(c)
\(S({\textsf{C}}_{n},4) > 8 S({\textsf{C}}_{n},3) \).
Proof
The values in Table 1 show that the inequalities are satisfied for \(n=9\). For larger values of n, we proceed by induction. Note that (a) and (b) are clearly valid for \(k=3\) since \(S({\textsf {C}}_{n},3)> 3 \ge \max \{S({\textsf {C}}_{n},2)),3S({\textsf {C}}_{n-1},2)\} \). We may therefore assume \(k\in \{4,5\}\) for (a) and \(k\in \{4,5,6\}\) for (b). Lemma 7 and the induction hypothesis imply
Hence (a) is proved. It follows that the following inequality is valid:
which implies
Hence (b) is proved. We thus have
which proves (c). \(\square \)
4 Upper Bounds on \({\mathcal {A}}(G)\)
We are now ready to give upper bounds on \({\mathcal {A}}(G)\). The following theorem gives a general upper bound on \({\mathcal {A}}(G)\) that is valid for all graphs G of order n.
Theorem 11
Let G be a graph of order n, then,
with equality if and only if \(G \simeq {\textsf {K}}_{n}\).
Proof
Clearly,
Hence, \({\mathcal {A}}(G)\le n\), with equality if and only if \(S(G,k)=0\) for all \(k<n\), that is if \(G\simeq {\textsf {K}}_{n}\). \(\square \)
Since \(\Delta ({\textsf {K}}_{n})=n-1\) we immediately get the following corollary to Theorem 11.
Corollary 12
Let G be a graph of order n and maximum degree \(\Delta (G)=n-1\). Then, \({\mathcal {A}}(G) \le n,\) with equality if and only if \(G \simeq {\textsf{K}}_{n} \).
We now give a more precise upper bound on \({\mathcal {A}}(G)\) for graphs G of order n and maximum degree \(\Delta (G)=n-2\).
Theorem 13
Let G be a graph of order \(n \ge 2\) and maximum degree \(\Delta (G)=n-2\). Then,
with equality if and only if \(G\simeq {\textsf{K}}_{n-1} \cup {\textsf{K}}_{1}\).
Proof
We have
Hence, \({\mathcal {A}}(G)\le n-1+\frac{1}{{{\mathcal {B}}}(G)}\), with possible equality only if \(S(G,k)=0\) for all \(k<n-1\). It is proved in [9] that \({{\mathcal {B}}}(G) \ge n\), with equality if and only if G is isomorphic to \({\textsf {K}}_{n-1} \cup {\textsf {K}}_{1}\) when \(n\ne 4\), and G is isomorphic to \({\textsf {K}}_{3} \cup {\textsf {K}}_{1} \) or \({\textsf {C}}_{4} \) when \(n=4\). Since \(S({\textsf {C}}_{4},2)=1>0 \) while \(S({\textsf {K}}_{n-1} \cup {\textsf {K}}_{1},k)=0 \) for all \(k<n-1\), we conclude that \({\mathcal {A}}(G) \le n-1 + \frac{1}{n} = \frac{n^2 - n + 1}{n}\), with equality if and only if \(G\simeq {\textsf {K}}_{n-1} \cup {\textsf {K}}_{1}\). \(\square \)
The next simple case is when \(\Delta (G)=1\).
Theorem 14
Let G be a graph of order n and maximum degree \(\Delta (G) = 1\). Then,
with equality if and only if \(G\simeq {\lfloor }{\frac{n}{2}}{\rfloor } {\textsf{K}}_{2}\cup (n\bmod 2){\textsf{K}}_{1} \).
Proof
If G contains two isolated vertices u and v, we know from Proposition 2 that \({\mathcal {A}}(G+uv)>{\mathcal {A}}(G)\). Hence the maximum value of \({\mathcal {A}}(G)\) is reached when G contains at most one isolated vertex, that is \(G\simeq {\lfloor }{\frac{n}{2}}{\rfloor } {\textsf {K}}_{2}\cup (n\bmod 2){\textsf {K}}_{1} \). \(\square \)
We now give a precise upper bound on \({\mathcal {A}}(G)\) for graphs G with maximum degree 2. We first analyze the impact of the replacement of an induced \({\textsf {C}}_{n} \) (\(n\ge 6\)) by \({\textsf {C}}_{n-3}\cup {\textsf {C}}_{3} \).
Lemma 15
\({\mathcal {A}}(G \cup {\textsf{C}}_{n}) < {\mathcal {A}}(G \cup {\textsf{C}}_{n-3} \cup {\textsf{C}}_{3}) \) for all \(n\ge 6\) and all graphs G.
Proof
We know from Lemma 6 (a), (b) and (c) that the result is true for \(n=6,7,8\). We can therefore assume \(n\ge 9\).
Let \(f_n(k,k') = S(\textsf{C}_{n-3} \cup \textsf{C}_{3},k)S(\textsf{C}_{n},k')-S(\textsf{C}_{n},k)S(\textsf{C}_{n-3} \cup \textsf{C}_{3},k')\). Proposition 5 shows that it is sufficient to prove that \(f_n(k,k')\ge 0\) for all \(k > k'\), the inequality being strict for at least one pair \((k,k')\). Note that \(f_n(n,2)=1>0\) for n even. Also, \(f_n(n,3)>0\) for n odd. Indeed, this is true for \(n=9\) since the values in Table 1 give \(f_n(9,3)=85-66=19\). For larger odd values of n, we proceed by induction, using Lemmas 7 and 8:
Hence, it remains to prove that \(f_n(k,k')\ge 0\) for all \(1\le k' < k \le n\). Let us start with the cases where \(k'\le 2\) and where \(k\ge n-1\).
-
If \(k'\le 2\) then \(f_n(k,k')=S({\textsf {C}}_{n-3} \cup {\textsf {C}}_{3},k)S({\textsf {C}}_{n},k')\ge 0 \).
-
If \(k \ge n-1\) then \(S({\textsf {C}}_{n},k) = S({\textsf {C}}_{n-3} \cup {\textsf {C}}_{3},k) \) since
-
\(S({\textsf {C}}_{n},n) = S({\textsf {C}}_{n-3} \cup {\textsf {C}}_{3},n)=1 \), and
-
\(S({\textsf {C}}_{n},n-1) = S({\textsf {C}}_{n-3} \cup {\textsf {C}}_{3},n-1)=\frac{n^2-3n}{2} \).
Also, it follows from Lemma 9 that \(S({\textsf {C}}_{n-3}\cup {\textsf {C}}_{3},k')=S({\textsf {Q}}_{n},k')-(-1)^{n}\rho _{k'} \) and Eqs. (1) and (2) give
$$\begin{aligned} \begin{aligned} S({\textsf {C}}_{n},k')&=S({\textsf {P}}_{n},k')-S({\textsf {C}}_{n-1},k')\\ {}&=\left( S({\textsf {Q}}_{n},k')+S({\textsf {P}}_{n-1},k')\right) -\left( S({\textsf {P}}_{n-1},k')-S({\textsf {C}}_{n-2},k')\right) \\ {}&=S({\textsf {Q}}_{n},k')+S({\textsf {C}}_{n-2},k'). \end{aligned} \end{aligned}$$Altogether, this gives
$$\begin{aligned} \begin{aligned} f_n(k,k')&= S({\textsf {C}}_{n},k)\Big (S({\textsf {C}}_{n},k')-\ S({\textsf {C}}_{n-3}\cup {\textsf {C}}_{3},k')\Big )\\ {}&=S({\textsf {C}}_{n},k)\Big (\big (S({\textsf {Q}}_{n},k')+S({\textsf {C}}_{n-2},k')\big )- \big (S({\textsf {Q}}_{n},k')-(-1)^{n}\rho _{k'}\big )\Big )\\ {}&=S({\textsf {C}}_{n},k)\Big (S({\textsf {C}}_{n-2},k')+(-1)^{n}\rho _{k'}\Big ). \end{aligned} \end{aligned}$$Hence,
-
if n is even then \(f_n(k,k')\ge 0\);
-
if n is odd and \(k'\notin \{3,4\}\) then \(f_n(k,k')\ge 0\);
-
if n is odd and \(k'=3\) then \(f_n(k,k')=S({\textsf {C}}_{n},k)(S({\textsf {C}}_{n-2},3)-2)\ge 0 \);
-
if n is odd and \(k'=4\) then \(f_n(k,k')=S({\textsf {C}}_{n},k)(S({\textsf {C}}_{n-2},4)-1)\ge 0 \).
-
We can therefore assume \(3 \le k' < k \le n-2\) and we finally prove that
The values in the following table, computed with the help of those for \({\textsf {C}}_{9} \) and \({\textsf {C}}_{6}\cup {\textsf {C}}_{3}\) in Table 1, show that this is true for \(n=9\):
\((k,k')\) | (4,3) | (5,3) | (5,4) | (6,3) | (6,4) | (6,5) | (7,3) | (7,4) | (7,5) | (7,6) |
---|---|---|---|---|---|---|---|---|---|---|
\(f_9(k,k')\) | 8100 | 21973 | 55923 | 16366 | 53466 | 32046 | 4589 | 16239 | 12369 | 2520 |
\(7S({\textsf {C}}_{9},k) \) | 5145 | 9849 | 9849 | 6468 | 6468 | 6468 | 1722 | 1722 | 1722 | 1722 |
For larger values of n, we proceed by induction. Lemmas 7 and 8 give
Since \(\delta _{k}=0\) for \(k\ge 6\) and \(f_{n-1}(k,k')\ge 0\), \(f_{n-1}(k-1,k')\ge 0\), \(f_{n-1}(k,k'-1)\ge 0\), and \(f_{n-1}(k-1,k'-1)\ge 0\) for \(k>k'\), we have \(f_n(k,k')\ge 0\) for \(k>k'\ge 6\).
Therefore, it remains to show that \(f_n(k,k')\ge 7S({\textsf {C}}_{n},k)\) for \(k' \in \{3,4,5\}\). Let \(g_n(k,k')=(-1)^n\delta _{k'}S({\textsf {C}}_{n},k)-(-1)^n\delta _kS({\textsf {C}}_{n},k')\). There are 4 possible cases.
-
Case 1: \(k'\in \{4,5\}\) and \(k\ge k'+2.\)
We have \(g_n(k,k')=(-1)^n\delta _{k'}S({\textsf {C}}_{n},k)\ge -6S({\textsf {C}}_{n},k)\). Using the induction hypothesis and Lemma 7, Eq. (5) gives
$$\begin{aligned} \begin{aligned} f_n(k,k') \ge&\Big (7(k-1)(k'-1)S({\textsf {C}}_{n-1},k)+7(k'-1)S({\textsf {C}}_{n-1},k-1)\Big )\\ {}&+\Big (7(k-1)S({\textsf {C}}_{n-1},k)+7S({\textsf {C}}_{n-1},k-1)\Big )-6S({\textsf {C}}_{n},k)\\ =&~7(k'-1)S({\textsf {C}}_{n},k)+7S({\textsf {C}}_{n},k)-6S({\textsf {C}}_{n},k) \\>&7S({\textsf {C}}_{n},k). \end{aligned} \end{aligned}$$ -
Case 2: \(k'\in \{4,5\}\) and \(k=k'+1.\)
Let us first give a lower bound on \(g_n(k,k')\):
-
if n is even and \(k=6\), then \(g_n(k,k')\ge 0\);
-
if n is even and \(k=5\), then \(g_n(k,k')\ge -S({\textsf {C}}_{n},4) \), and we deduce from Lemma 10 (a) that \(g_n(k,k')\ge -S({\textsf {C}}_{n},5) \);
-
if n is odd, then \(g_n(k,k')\ge -\delta _{k'}S({\textsf {C}}_{n},k)\ge -6S({\textsf {C}}_{n},k) \).
Hence, whatever n and \((k,k')\), \(g_n(k,k')\ge -6S({\textsf {C}}_{n},k) \). Since \(f_{n-1}(k-1,k')=0\), using again the induction hypothesis and Lemma 7, we deduce from Eq. (5) that
$$\begin{aligned}\begin{aligned} f_n(k,k') \ge&\Big (7(k{-}1)(k'{-}1)S({\textsf {C}}_{n{-}1},k)\Big ) {+}\Big (7(k{-}1)S({\textsf {C}}_{n{-}1},k){+}7S({\textsf {C}}_{n{-}1},k{-}1)\Big ){-}6S({\textsf {C}}_{n},k)\\ =&~\Big (7(k'-1)S({\textsf {C}}_{n},k)-7(k'-1)S({\textsf {C}}_{n-1},k-1)\Big )+\Big (7S({\textsf {C}}_{n},k)\Big )-6S({\textsf {C}}_{n},k)\\ =&~(7k'-6)S({\textsf {C}}_{n},k)-7(k'-1)S({\textsf {C}}_{n-1},k-1). \end{aligned} \end{aligned}$$Since \(k\le 6\), Lemma 10 (b) shows that \(S({\textsf {C}}_{n-1},k-1)\le \frac{1}{3}S({\textsf {C}}_{n},k) \) and we therefore have
$$\begin{aligned} \begin{aligned}f_n(k,k')&\ge \left( \frac{14k'-11}{3}\right) S({\textsf {C}}_{n},k)\\ {}&>7S({\textsf {C}}_{n},k).\end{aligned} \end{aligned}$$ -
-
Case 3: \(k'=3\) and \(k\ge 5.\)
As in the previous case, we have \(g_n(k,k')\ge -6S({\textsf {C}}_{n},k) \). The induction hypothesis gives \(f_{n-1}(k,k')\ge 7S({\textsf {C}}_{n-1},k) \), \(f_{n-1}(k-1,k')\ge 7S({\textsf {C}}_{n-1},k-1) \), \(f_{n-1}(k,k'-1){\ge } 0\), and \(f_{n-1}(k-1,k'-1)\ge 0\). Hence, Eq. (5) becomes
$$\begin{aligned} \begin{aligned} f_n(k,k') \ge&7(k-1)(k'-1)S({\textsf {C}}_{n-1},k)+7(k'-1)S({\textsf {C}}_{n-1},k-1)-6S({\textsf {C}}_{n},k)\\ =&~7(k'-1)S({\textsf {C}}_{n},k)-6S({\textsf {C}}_{n},k)\\ >&7S({\textsf {C}}_{n},k). \end{aligned} \end{aligned}$$ -
Case 4: \(k'=3\) and \(k=4.\)
We have \(g_n(k,k')=(-1)^n6S({\textsf{C}}_{n},k)-(-1)^n6S({\textsf{C}}_{n},k') \) and we know from Lemma 10 (a) that \(S({\textsf{C}}_{n},4)>S({\textsf{C}}_{n},3)\). Hence, \(g_n(4,3)\ge -6(S({\textsf{C}}_{n},k)-S({\textsf{C}}_{n},k'))\). Using the induction hypothesis, Eq. (5) gives
$$\begin{aligned}\begin{aligned} f_n(k,k')&\ge -7(k-1)(k'-1)S({\textsf {C}}_{n-1},k)-6\Big (S({\textsf {C}}_{n},k)-S({\textsf {C}}_{n},k')\Big )\\ {}&=42S({\textsf {C}}_{n-1},k)-6\Big (S({\textsf {C}}_{n},k)-S({\textsf {C}}_{n},k')\Big ).\end{aligned} \end{aligned}$$We therefore conclude from Lemmas 7 and 10 (c) that
$$\begin{aligned}\begin{aligned}f_n(4,3)&\ge \frac{42}{3}\Big (S({\textsf {C}}_{n},4)-S({\textsf {C}}_{n},3\Big )-6\Big (S({\textsf {C}}_{n},4)-S({\textsf {C}}_{n},3)\Big )\\ {}&=8\Big (S({\textsf {C}}_{n},4)-S({\textsf {C}}_{n},3)\Big )\\ {}&>8\Big (S({\textsf {C}}_{n},4)-\frac{1}{8}S({\textsf {C}}_{n},4)\Big )\\ {}&=7S({\textsf {C}}_{n},4). \end{aligned} \end{aligned}$$
\(\square \)
We now study the impact of the replacement of an induced \({\textsf {K}}_{3}\cup {\textsf {K}}_{1} \) by \({\textsf {C}}_{4} \). It is easy to check that
-
\({\mathcal {A}}({\textsf{K}}_{3}\cup {\textsf{K}}_{1})=\frac{13}{4}>3={\mathcal {A}}({\textsf{C}}_{4}) \), and
-
\({\mathcal {A}}(2{\textsf{K}}_{3}\cup {\textsf{K}}_{1})=\frac{778}{175}>\frac{684}{154}={\mathcal {A}}({\textsf{K}}_{3}\cup {\textsf{C}}_{4}) \).
Hence, \({\mathcal {A}}((p+1)\textsf{K}_{3}\cup \textsf{K}_{1})>{\mathcal {A}}(p\textsf{K}_{3}\cup \textsf{C}_{4})\) for \(p=0,1\). We next prove that this inequality is reversed for larger values of p, that is \({\mathcal {A}}((p+1)\textsf{K}_{3}\cup \textsf{K}_{1})<{\mathcal {A}}(p\textsf{K}_{3}\cup \textsf{C}_{4})\) for \(p\ge 2\). Proposition 5 is of no help for this proof since, whatever p, there are pairs \((k,k')\) for which \(S((p+1){\textsf {K}}_{3}\cup {\textsf {K}}_{1},k) S(p{\textsf {K}}_{3}\cup {\textsf {C}}_{4},k') > S(p{\textsf {K}}_{3}\cup {\textsf {C}}_{4},k)S((p+1){\textsf {K}}_{3}\cup {\textsf {K}}_{1},k') \), and other pairs for which the inequality is reversed. Also, it is not true that
which would have given a simple proof by induction on p. The only way we have found to prove the desired result is to explicitly calculate \({\mathcal {A}}((p+1){\textsf {K}}_{3}\cup {\textsf {K}}_{1}) \) and \({\mathcal {A}}(p{\textsf {K}}_{3}\cup {\textsf {C}}_{4}) \). This is what we do next, with the help of two lemmas.
Lemma 16
If G is a graph of order n, then
Proof
As observed in [9],
Hence,
and
The values for \({{\mathcal {B}}}(G \cup {\textsf {K}}_{3}) \) and \({{\mathcal {T}}}(G \cup {\textsf {K}}_{3}) \) are computed in a similar way. \(\square \)
Lemma 17
If G is a graph of order n, then,
Proof
Let \(G' = G \cup {\textsf {K}}_{3} \). Equation (6) gives \(S(G' \cup {\textsf {K}}_{1}, k) = k S(G',k) + S(G',k-1) \). Hence, it follows from Lemma 16 that
Equation (6) gives
Hence, using again Lemma 16, we get
\(\square \)
We are now ready to compare \({\mathcal {A}}(p {\textsf {K}}_{3}\cup {\textsf {C}}_{4}) \) with \({\mathcal {A}}((p+1) {\textsf {K}}_{3}\cup {\textsf {K}}_{1}) \).
Lemma 18
-
\({\mathcal {A}}(p {\textsf{K}}_{3}\cup {\textsf{C}}_{4})<{\mathcal {A}}((p+1) {\textsf{K}}_{3}\cup {\textsf{K}}_{1}) \) if \(p=0,1\) and
-
\({\mathcal {A}}(p {\textsf{K}}_{3}\cup {\textsf{C}}_{4})>{\mathcal {A}}((p+1) {\textsf{K}}_{3}\cup {\textsf{K}}_{1}) \).
Proof
We have already mentioned that the lemma is valid for \(p=0,1\). Hence, it remains to prove that \({\mathcal {A}}(p {\textsf {K}}_{3}\cup {\textsf {C}}_{4})>{\mathcal {A}}((p+1) {\textsf {K}}_{3}\cup {\textsf {K}}_{1}) \) for \(p\ge 2\). So assume \(p\ge 2\) and let
Since
we have to prove that \(f(p)>0\). Note that Eqs. (1) and (2) give
which implies
Hence, with \(G=p\textsf{K}_{3}\), we get
Since \(S(G,k)=0\) for \(k<3\), we deduce from Lemmas 16 and 17 that
where
-
\(\begin{array}{ll}a_k&= k^4 + k^3 + 5k^2 + 6k + 4\end{array}\),
-
\(\begin{array}{ll}b_k&= -k^4 + k^3 -4k^2 - k - 1,\end{array}\)
-
\(\begin{array}{ll}c_k&= k^5 + k^4 + 9k^3 + 15k^2 + 21k + 13\end{array}\), and
-
\(\begin{array}{ll}d_k&= -k^3+k^2-k.\end{array}\)
It is therefore sufficient to prove that the sums defined at (7) and (8) are strictly positive.
-
Let \(g(k) = a_k b_k - c_k d_k= k^6 + k^5 - 5k^4 - 19 k^3 - 19k^2 + 3k - 4\). It can be checked that \(g(k)>0\) for all \(k>3\). Note that Eq. (6) gives
$$\begin{aligned} S(G,3)=&~S(p\textsf{K}_{3},3)=6S((p-1)\textsf{K}_{3},3)\\ <&18S(p-1)\textsf{K}_{3},3)+24S((p-1)\textsf{K}_{3},4) \\ =&~S((p\textsf{K}_{3},4)=S(G,4).\end{aligned}$$Since \(g(3)=-112\) and \(g(4) = 2328\), we have \(g(3)S^2(G, 3)+g(4)S^2(G, 4)>0\), which implies
$$\begin{aligned} \sum _{k=3}^n (a_k b_{k} {-} c_k d_{k}) S^2(G, k)= g(3)S^2(G, 3)+g(4)S^2(G, 4)+\sum _{k=5}^n g(k) S^2(G, k)>0. \end{aligned}$$Hence, the sum in (7) is strictly positive.
-
Let \(h(k',k)=a_k b_{k'} - c_k d_{k'}+a_{k'} b_{k} - c_{k'} d_{k}.\) By definition of \(a_k, b_k, c_k\) and \(d_k\) we obtain
$$\begin{aligned} h(k',k) =&~ \ {\left( {k}^{3} - {k}^{2} + {k}\right) } {k'}^{5} \\ {}&- {\left( 2 {k}^{4} - {k}^{3} + 10 {k}^{2} + 6 {k} + 5\right) } {k'}^{4}\\&+ {\left( {k}^{5} + {k}^{4} + 20 {k}^{3} + 7 {k}^{2} + 35 {k} + 16\right) } {k'}^{3} \\ {}&- {\left( {k}^{5} + 10 {k}^{4} - 7 {k}^{3} + 70 {k}^{2} + 35 {k} + 34\right) } {k}'^{2} \\&+ {\left( {k}^{5} - 6 {k}^{4} + 35 {k}^{3} - 35 {k}^{2} + 30 {k} + 3\right) } {k'} \\ {}&- 5 {k}^{4} + 16 {k}^{3} - 34 {k}^{2} + 3 {k} - 8. \end{aligned}$$Let us make a change of variable. More precisely, we substitute \(k'\) by \(i+3\) and k by \(j+i+4\). Since \(k'\ge 3\) and \(k\ge k'+1\), we get \(i\ge 0\) and \(j\ge 0\). It is a tedious but easy exercise to check that with these new variables, \(h(k',k)=h(i{+}3,j{+}i{+}4)=h'(i,j)\) with
$$\begin{aligned} h'(i, j) =&~{\left( j^{2} + 2j + 3\right) } i^{6} + {\left( 3j^{3} + 25j^{2} + 47j + 63\right) } i^{5}\\ {}&+ {\left( 3j^{4} + 52j^{3} + 243j^{2} + 437j + 533\right) } i^{4}\\&+ {\left( j^{5} + 37j^{4} + 338j^{3} + 1154j^{2} + 2017j + 2267\right) } i^{3} \\&+ {\left( 8j^{5} + 161j^{4} + 997j^{3} + 2713j^{2} + 4692j + 4873\right) } i^{2} \\&+ {\left( 22j^{5} + 290j^{4} + 1258j^{3} + 2729j^{2} + 4784j + 4443\right) } i \\&+ 21j^{5} + 172j^{4} + 440j^{3} + 575j^{2} + 1112j + 602. \end{aligned}$$Since \(i\ge 0\), \(j\ge 0\), and all coefficients in \(h'(i, j)\) are positive, we conclude that \(h'(i,j)=h(k',k) > 0\) for \(3\le k'<k\le n\).
Hence, the sum \(\displaystyle \sum _{k'=3}^{n-1}\sum _{k=k'+1}^nh(k',k)S(G, k) S(G, k')\) in (8) is strictly positive.
\(\square \)
We are now ready to prove the main result of this section, where \({\textsf{U}_{n}}\) (\(n \ge 3\)) is the graph defined in Sect. 2.
Theorem 19
If G is a graph of order \(n \ge 3\) and maximum degree \(\Delta (G)=2\), then \({\mathcal {A}}(G) \le \mathcal {A}(\textsf{U}_n) \), with equality if and only if \(G\simeq \textsf{U}_n\).
Proof
Since \(\Delta (G) = 2\), G is a disjoint union of cycles and paths. Now, suppose that G maximizes \({\mathcal {A}}\) among all graphs of maximum degree 2. Then at most one connected component of G is a path. Indeed, if \(G\simeq G'\cup {\textsf {P}}_{k}\cup {\textsf {P}}_{k'}\), then Eqs. (3) and (4) give \({{\mathcal {B}}}(G'\cup {\textsf {P}}_{k}\cup {\textsf {P}}_{k'})={{\mathcal {B}}}(G'\cup {\textsf {P}}_{k+k'})+{{\mathcal {B}}} (G'\cup {\textsf {P}}_{k+k'-1})\) and \({{\mathcal {T}}}(G'\cup {\textsf {P}}_{k}\cup {\textsf {P}}_{k'})={{\mathcal {T}}}(G'\cup {\textsf {P}}_{k+k'})+{{\mathcal {T}}}(G'\cup {\textsf {P}}_{k+k'-1})\). Moreover, we know from Proposition 2 that \({\mathcal {A}}(G'\cup {\textsf {P}}_{k+k'-1})<{\mathcal {A}}(G'\cup {\textsf {P}}_{k+k'})\). Hence, Proposition 4 implies that \({\mathcal {A}}(G)={\mathcal {A}}(G'\cup {\textsf {P}}_{k}\cup {\textsf {P}}_{k'})<{\mathcal {A}}(G'\cup {\textsf {P}}_{k+k'})\). Since \((G'\cup {\textsf {P}}_{k+k'})\) is of order n and maximum degree 2, this contradicts the hypothesis that G maximizes \({\mathcal {A}}\).
We know from Lemma 3 that replacing a path \({\textsf {P}}_{k}\) of order \(k \ge 3\) by a cycle \({\textsf {C}}_{k}\) strictly increases \({\mathcal {A}}(G)\). Moreover, Lemma 15 shows that replacing a cycle \({\textsf {C}}_{k}\) of order \(k \ge 6\) by \({\textsf {C}}_{k-3} \cup {\textsf {K}}_{3}\) increases \({\mathcal {A}}(G)\). Hence G is a disjoint union of copies of \(\textsf{K}_{3}\), \(\textsf{C}_{4}\) and \(\textsf{C}_{5}\) and eventually one path that is either \(\textsf{K}_{1}\) or \(\textsf{K}_{2}\).
Considering Lemma 6, we know from (d), (e) and (f) that G does not contain \(\textsf{K}_{2}\), and from (g)-(k) that at most one connected component of G is not a \(\textsf{K}_{3}\). Hence, if \(n \bmod 3=0\) then \(G\simeq \frac{n}{3} \textsf{K}_{3}\) and if \(n \bmod 3=2\) then \(G\simeq \frac{n-5}{3} \textsf{K}_{3} \cup \textsf{C}_{5}\). Finally, Lemma 18 shows that \(G\simeq \frac{n-1}{3}\textsf{K}_{3} \cup \textsf{K}_{1}\) if \(n = 4\) or 7, and \(G\simeq \frac{n-4}{3} \textsf{K}_{3} \cup \textsf{C}_{4}\) if \(n \bmod 3 = 1\) and \(n \ge 10\). \(\square \)
5 Concluding Remarks
We have given a general upper bound on \({\mathcal {A}}(G)\) that is valid for all graphs G, and a more precise one for graphs of order n and maximum degree \(\Delta (G)\in \{1,2,n-2\}\). Note that there is no known lower bound on \({\mathcal {A}}(G)\) which is a function of n and such that there exists at least one graph of order n which reaches it.
The problem of finding a tight upper bound for graphs with maximum degree in \(\{3,\ldots ,n-3\}\) remains open. Since all graphs of order n and maximum degree \(\Delta (G)\in \{1,n-2,n-1\}\) that maximize \({\mathcal {A}}(G)\) are isomorphic to \({\lfloor }{\tfrac{n}{\Delta (G)+1}}{\rfloor } \textsf{K}_{\Delta (G)+1}\cup \textsf{K}_{n\bmod (\Delta (G)+1)}\) (but this is not always true for \(\Delta (G)=2\)), one could be tempted to think that this is also true when \(3\le \Delta (G)\le n-3\). We have checked this statement by enumerating all graphs having up to 12 vertices, using PHOEG[2]. We have thus determined that there is only one graph of order \(n\le 12\) and \(\Delta (G)\ne 2\) (among more than 165 billion), namely \(\mathsf{{\overline{C}}}_{6} \cup \textsf{K}_{4}\), for which such a statement is wrong. Indeed, \({\mathcal {A}}(\mathsf{{\overline{C}}}_{6} \cup \textsf{K}_{4}) = 5.979 > 5.967={\mathcal {A}}(2 \textsf{K}_{4} \cup \textsf{K}_{2}) \), which shows that \(2 \textsf{K}_{4} \cup \textsf{K}_{2}\) does not maximize \({\mathcal {A}}(G)\) among all graphs of order 10 and maximum degree 3.
Availability of material and data
References
Absil, R., Camby, E., Hertz, A., and Mélot, H.: A sharp lower bound on the number of non-equivalent colorings of graphs of order n and maximum degree n-3. Discrete Appl. Math. 234, 3–11 (2018). (Special Issue on the Ninth International Colloquium on Graphs and Optimization (GO IX), 2014)
Devillez, G., Hauweele, P., Mélot, H.: PHOEG Helps to Obtain Extremal Graphs. In: Fortz, B., Labbé, M. (eds) Operations Research Proceedings 2018 (GOR (Gesellschaft fuer Operations Research e.V.)) (sept. 12–14 2019), Springer, Cham, p. 251 (Paper 32)
Diestel, R.: Graph Theory, 2nd ed. Springer (2017)
Dong, F. M., Koh, K. M., Teo, K. L.: Chromatic Polynomials and Chromaticity of Graphs. World Scientific Publishing Company (2005)
Duncan, B.: Bell and Stirling numbers for disjoint unions of graphs. Congressus Numerantium 206 (2010)
Duncan, B., Peele, R. B.: Bell and Stirling numbers for graphs. J. Integer Seq. 12, Article 09.7.1 (2009)
Galvin, D., Thanh, D.T.: Stirling numbers of forests and cycles. Electron. J. Comb. 20, Paper P73 (2013)
Hertz, A., Hertz, A., Mélot, H.: Using graph theory to derive inequalities for the Bell numbers. J. Integer Seq. 24, Article 21.10.6 (2021)
Hertz, A., Mélot, H.: Counting the number of non-equivalent vertex colorings of a graph. Discrete Appl. Math. 203, 62–71 (2016)
Hertz, A., Mélot, H., Bonte, S., Devillez, G.: Lower bounds and properties for the average number of colors in the non-equivalent colorings of a graph. Discrete Appl. Math. (2022). https://doi.org/10.1016/j.dam.2022.08.011
Kereskényi-Balogh, Z., Nyul, G.: Stirling numbers of the second kind and Bell numbers for graphs. Australas. J. Comb. 58, 264–274 (2014)
Odlyzko, A., Richmond, L.: On the number of distinct block sizes in partitions of a set. J. Comb. Theory Ser. A. 38(2), 170–181 (1985)
Sloane, N.: The on-line encyclopedia of integer sequences. http://oeis.org
Acknowledgements
The authors thank Julien Poulain for his precious help in optimizing our programs allowing us to check our conjectures on a large number of graphs.
Funding
Computational resources have been provided by the Consortium des Équipements de Calcul Intensif (CÉCI), funded by the Fonds de la Recherche Scientifique de Belgique (F.R.S.-FNRS) under Grant No. 2.5020.11 and by the Walloon Region.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have not disclosed any competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Hertz, A., Mélot, H., Bonte, S. et al. Upper Bounds on the Average Number of Colors in the Non-equivalent Colorings of a Graph. Graphs and Combinatorics 39, 49 (2023). https://doi.org/10.1007/s00373-023-02637-9
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-023-02637-9