Weighted graphs: Eigenvalues and chromatic number

Electronic Journal of Graph Theory and Applications

C. Delorme

University Paris Sud 91405 Orsay CEDEX - France.

Charles.Delorme@lri.fr

We revisit Hoffman relation involving chromatic number \(\chi\) and eigenvalues. We construct some graphs and weighted graphs such that the largest and smallest eigenvalues \(\lambda\) dan \(\mu\) satisfy \(\lambda=(1-\chi)\mu\). We study in particular the eigenvalues of the integer simplex \(T_m^2\), a 3-chromatic graph on \(\binom{m+2}{2}\) vertices.

Keywords: chromatic number, eigenvalues, weighted graphs Mathematics Subject Classification : 05C22, 05C50

DOI: 10.5614/ejgta.2016.4.1.2

1. Chromatic number and eigenvalues

Proposition 1.1. (a variant of Hoffman's [4]) Let G be a connected graph, whose edges may have positive weights, endowed with a proper coloration using \(\chi\) colors. Let \(G_{ij}\) be the bipartite graph induced in G by the two color classes i and j. Let \(K_1 \geq K_2 \geq \cdots \geq K_{\chi(\chi-1)/2}\) be the largest eigenvalues of the \(\chi(\chi-1)/2\) bipartite graphs \(G_{ij}\). The largest adjacency eigenvalue \(\lambda\) of G is at most the sum \(\sum_{i=1}^{\chi-1} K_i\) of the \(\chi-1\) largest eigenvalues of the bipartite graphs. As a corollary, \(\lambda \leq -(\chi-1)\mu\), where \(\mu\) is the smallest eigenvalue of G. Moreover, if \(\lambda = -(\chi-1)\mu\), all bipartite graphs defined by two colors have extremal eigenvalues \(\mu\) and \(\mu\).

Proof. Various proofs for unweighted graphs were given by Godsil ([2], p. 1733) and Haemers [3]. The inequality admits refinements: \(2\lambda\) is at most the sum of the \(\chi\) largest singular values (see [7]).

Received: 17 March 2014, Accepted: 05 January 2015.

We will use only singular values (see [6]), interlacing of adjacency values (see [3]) and Gershgorin inequalities (see [5]).

Consider a partition of the vertices in \(\chi\) coloration classes. Consider the blocks \(A_{i,j}\) induced by the color partition in the adjacency matrix of the graph G. Thus each diagonal block \(A_{i,i}\) is null because the coloration classes are stable subsets.

Let us use the norms defined as the highest singular value of the matrices (or rows, or columns), in other words the Ky Fan norm \(\|\cdot\|_{F_1}\). For rows and columns, it coincides with the euclidian norm: for matrices it coincides with the corresponding matrix norm. For symmetric real matrices: it is the highest eigenvalue (see [6] p. 171).

The largest eigenvalue \(\lambda\) of G defines a unit length eigenvector with only positive components, also partitioned into blocks \(V_i\). We have then \(\sum |V_i|^2 = 1\) and \(\lambda = \sum_{i,j} V_i^t A_{i,j} V_j\). Thus \(|V_i^t| = |V_i|\) and \(|V_i^t A_{i,j} V_j| \leq |V_i| |A_{i,j}| |V_j|\) and therefore we have \(\lambda \leq \sum_{i,j} |V_i^t| |A_{i,j}| |V_j|\).

We consider the square matrix of size \(\chi\) and entries \(|A_{i,j}|\). According to Gershgorin method, the largest eigenvalue is at most the largest sum of entries in a row (recall that the entries are \(\geq 0\)). Thus it is at most \(\sum_{i=1}^{\chi-1} K_i\). On the other hand, \(K_1\) is the maximum eigenvalue of some induced bipartite graph \(G_{ij}\) induced by classes i and j, and thus \(-K_1\) is the smallest eigenvalue of \(G_{ij}\): then interlacing ensures \(\mu \leq -K_1\). Clearly \(0 < K_1 \leq -\mu\) and \(0 < \lambda \leq (\chi-1)K_1\) imply \(\lambda \leq -\mu(\chi-1)\). More precisely, if \(\lambda = (1-\chi)\mu\), we see from Gershgorin method that all bipartite subgraphs defined by pairs of colors have the same largest and smallest eigenvalue, namely \(-\mu\) and \(\mu\) and that all vectors \(V_i\) have the same norm. Thus, if \(\lambda = (1-\chi)\mu\) then \(\mu\) has multiplicity at least \(\chi-1\) in the spectrum of G (see also [4]).

Example 1. Both inequalities \(\mu \leq -K_1\) and \(\lambda \leq K_1 + K_2\) for 3-colorable graphs could be equalities or strict inequalities. Here are four examples with planar and uniquely 3-colorable graphs, that is, there is only one partition of the vertices into three stable sets. See Figure 1.

Figure 1. Four uniquely 3-colorable graphs

The octahedron has \(-2 = \mu = -K_1 = -K_2 = -\lambda/2\). More generally, the regular complete tripartite graph \(K_{m,m,m}\) has \(-m = \mu = -K_1 = -K_2 = -\lambda/2\) and all other eigenvalues are null.

The suspension of a 6-cycle has eigenvalues (with multiplicities) in decreasing order \(\{1 + \sqrt{7}, 1^{[2]}, (-1)^{[2]}, 1 - \sqrt{7}, -2\}\). The bipartite graphs are the 6-cycle with eigenvalues \(\{2, 1^{[2]}, (-1)^{[2]}, -2\}\) and two copies of \(K_{1,3}\) with eigenvalues \(\{\sqrt{3}, 0^{[2]}, -\sqrt{3}\}\). Thus \(\mu = -K_1 = -2\) and \(\lambda = 1 + \sqrt{7} < K_1 + K_2 = 2 + \sqrt{3}\).

The antiprism on a 9-gon has spectrum \(\{2\cos(\frac{k\pi}{9})+2\cos(\frac{2k\pi}{9}), k=0..17\}\) (not ordered). The largest eigenvalue is \(\lambda=4\), the smallest is \(2\cos(\frac{5\pi}{9})+2\cos(\frac{10\pi}{9})<-2\). The bipartite graphs

are 12-cycles, with smallest eigenvalue -2. Hence \(\mu = 2\cos(\frac{5\pi}{9}) + 2\cos(\frac{10\pi}{9}) < -2 = -K_1 = -K_2 = -\lambda/2\).

Even if the three bipartite graphs are isomorphic and connected, we may find \(\mu < K_1 < -\lambda/2\), as shown in the last example. The bipartite graphs are paths on 4 vertices with the smallest eigenvalue \((-1-\sqrt{5})/2 \simeq -1.618\). But the characteristic polynomial of the graphs is \((X^3-X^2-6X-3)(X^3+X^2-2X-1)\), its smallest root is \(\mu \simeq -1.80 < (-1-\sqrt{5})/2\) and its largest \(\lambda \simeq 3.18 < 1+\sqrt{5}\).

Remark 1.1. It is not surprising that the inequality is also obtained for some graphs, even connected ones, that are not 3-colorable. For example, the antiprism on a 5-gon has spectrum \(\{4, (\sqrt{5})^{[2]}, 0, (-1)^{[4]}, (-\sqrt{5})^{[2]}\}\); thus \(\mu < -\lambda/2\), but the graph is not 3-colorable.

Even unique colorability does not help: the join of \(K_q\) and \(\overline{K_p}\) (with p and \(q \geq 2\)) is uniquely (q+1)-colorable, but the largest eigenvalue is \(\lambda = \frac{q-1+\sqrt{(q-1)^2+4pq}}{2}\) and the smallest \(\mu = \frac{q-1-\sqrt{(q-1)^2+4pq}}{2}\). (The other eigenvalues are 0 and -1 with multiplicities p-1 and q-1). The ratio \(\lambda/\mu\) tends to -1 when \(p \to \infty\).

2. Weighted graphs with \(\lambda = (1 - \chi)\mu\)

2.1. General constructions

Obviously, multiplication by a positive real of all weights preserve the property. We observe that if we cut a symmetric matrix into blocks, say

\[M = \begin{bmatrix} M_{11} & M_{12} \\ M_{21} & M_{22} \end{bmatrix},\]

with \(M_{11}\) and \(M_{22}\) square, of sizes \(n_1\) and \(n_2\), the matrix of size \(n_1 + nn_2\)

\[\begin{bmatrix} M_{11} & M_{12}/\sqrt{n} & M_{12}/\sqrt{n} & \cdots & M_{12}/\sqrt{n} \\ M_{21}/\sqrt{n} & M_{22} & 0 & \cdots & 0 \\ M_{21}/\sqrt{n} & 0 & \ddots & \ddots & \vdots \\ \vdots & \vdots & \ddots & M_{22} & 0 \\ M_{21}/\sqrt{n} & 0 & \cdots & 0 & M_{22} \end{bmatrix}\]

has spectrum the multiset union of the spectrum of M and n-1 copies of the spectrum of \(M_{22}\). Thus replication of parts of a (weighted) graph with \(\lambda = (1 - \chi \mu)\) and appropriate modifications of weights give new weighted graphs with the same property.

Using these two methods we obtain from the unweighted \(K_3\) some 3-colorable weighted graphs with \(\lambda = -2\mu\) (Figure 2). The unmarqued edges have weight 1.

The graph of order 4 has \(\lambda=2\sqrt{2}\); the ones of order 5 have (from left to right) \(\lambda=2\sqrt{2}, \lambda=2\sqrt{3}, \lambda=4\), and \(\lambda=2\sqrt{3}\). However the last graphs is not obtained by the same method. We now give some other graphs where Hoffman's inequality becomes an equality. If G has chromatic number \(\chi\) and satisfies \(\lambda_G=(1-\chi)\mu_G\); and if H is a connected graph with at least a loop and two vertices, such that \(\mu_H(\chi-1)\leq \lambda_H\), then the categorical product \(G\times H\) (called product in ([1],

Figure 2. Some weighted 3-colorable graphs with \(\lambda = -2\mu\)

p. 66) has also chromatic number \(\chi\) and satisfies \(\lambda_{G \times H} = (1 - \chi)\mu_{G \times H}\). Morever, with the same condition on H, if G is uniquely \(\chi\)-colorable, then \(G \times H\) is also uniquely \(\chi\)-colorable.

As an example, we show the product with G a triangle and H a path of length 2 with a loop at each vertex \((\lambda_H = \sqrt{2} + 1, \mu_H = 1 - \sqrt{2})\), (Figure 3 left) or a path of lengt h 2 with a loop at the central vertex \((\lambda_H = 2, \mu_H = 1)\), (Figure 3 right).

Figure 3. Two uniquely 3-colorable products with \(\lambda = -2\mu\)

The case of G and H complete graphs, with a loop at each vertex of H gives again the regular multipartite complete graphs. Some Cayley graphs have the property. For example the ones built on the groups \(\mathbb{Z}/3p\mathbb{Z}\times\mathbb{Z}/3pq\mathbb{Z}\) with generator \(\{\pm(1,0),\pm(0,1),\pm(1,1)\}\) and parameters \(\lambda=6,\mu=-3\), and \(\chi=3\).

2.2. Particular graphs

The two graphs of Figure 4 satisfy also the conditions

• uniquely 3-colorable,
• \(\lambda = -2\mu\) (here \(\lambda = 4\)),
• the bipartite graphs have smallest eigenvalue \(\mu\).

Figure 4. Two cospectral planar uniquely 3-colorable graphs with \(\lambda = -2\mu\)

Both graphs have spectrum \(\{4, \sqrt{2}^{[2]}, 0^{[2]}, (-\sqrt{2})^{[2]}, (-2)^{[2]}\}\). In the first graph the bipartite graphs are a 8-cycle and 2 copies of the extended Dynkin diagram \(\tilde{D}_4\) (alias \(K_{1,4}\)). In the second graph they are a 4-cycle and 2 copies of \(\tilde{D}_6\) (on 7 vertices).

In the same vein, we have a graph \(T_3^2\) (that will appear in Section 3) decomposable into \(C_6\) and two copies of \(\tilde{E}_6\). The cartesian product of two graphs of chromatic number \(\chi\) has also chromatic number \(\chi\). The condition \(\lambda = (1-\chi)\mu\) is also preserved by cartesian product, as well as connexity, but the unicity of the \(\chi\)-coloration is not (unless \(\chi \leq 2\)).

3. Integer simplexes of dimension 2

Here we describe a family of non-regular graphs with the property \(\lambda = -2\mu\), the integer simplexes of dimension 2, denoted \(T_m^2\), that are not regular if \(m \ge 2\) (see [8]).

Definition 1. The graph \(T_m^2\) is made from the \(\binom{m+2}{2}\) ordered triples of nonnegative integers with sum m. The edges connect vertices that differ by 1 in two places.

These graphs are uniquely 3-colorable for \(m \ge 1\); it suffices to give color \((u+2v) \mod 3\) to the vertex [m-u-v,u,v] and there is no other choice up to permutation of colors.

As a consequence, the isomorphism \([x,y,z] \mapsto [y,z,x]\) permutes the color classes if m is not multiple of 3, and stabilizes them if 3|m. Similarly, the isomorphism \([x,y,z] \mapsto [x,z,y]\) permutes the parts with colors 1 and 2 and stabilizes the part with color 0.

3.1. Relations

We will prove that the eigenvalues of these graphs satisfy not only the inequalities given in Section 1, but the equality \(\lambda = -2\mu\), and that \(\mu\), \(-\mu\) are the largest and smallest eigenvalues of the three bipartite graphs, even if m is multiple of 3, where the class of color 0 gives a bipartite graph with order \(\left(2 + \binom{m+2}{2}\right)/3\) and two (isomorphic) ones of order \(\left(-1 + \binom{m+2}{2}\right)/3\).

Proposition 3.1. The largest adjacency eigenvalue of \(T_m^2\) is \(\lambda = 2 + 4\cos(\frac{2\pi}{m+3})\), and \(-\lambda/2 = -1 - 2\cos(\frac{2\pi}{m+3})\) is an eigenvalue of \(T_m^2\).

Proof. We will consider the polynomials \(U_i\) defined by \(U_0 = 1\), \(U_1 = X\) and \(U_{n+2} = XU_{n+1} - U_n\). They satisfy the equalities of rational fractions \((X-1/X)U_n(X+1/X) = X^{n+1} - X^{-n-1}\) and thus the equalities \(U_n(2\cos\theta)\sin\theta = \sin((n+1)\theta)\). They are of course closely related to Chebyshev polynomials of second kind.

We consider also the polynomials \(P_{j,i}\) where i,j are integers with \(0 \le i \le j\) defined for \(0 \le i \le j/2\) by \(P_{j,i} = \sum_{i \le k \le j-i} (i+1)U_k + \sum_{0 \le k \le i-1} (k+1)(U_k + U_{j-k})\) and if \(j/2 \le i \le j\) by \(P_{j,i} = P_{j,j-i}\). For convenience, we add \(P_{j,-1} = P_{j,j+1} = 0\) for \(j \ge -1\). They satisfy for \(j \ge 0\) and 0 < i < j the equalities

\[(1+X)P_{j,i} = P_{j,i+1} + P_{j-1,i-1} + P_{j+1,i+1} = P_{j,i-1} + P_{j-1,i} + P_{j+1,i}\]

and therefore

\[(2+2X)P_{i,i} = P_{i,i+1} + P_{i,i-1} + P_{i-1,i-1} + P_{i-1,i} + P_{i+1,i+1} + P_{i+1,i}\]

They also satisfy \(P_{m+1,i}(2\cos(\frac{2t\pi}{m+3}))=0\) for \(0\leq i\leq m+1\) and \(1\leq t\leq (m+3)/2\), t integer. Indeed for \(\theta=\frac{2t\pi}{m+3}\) we have \(\sin\theta\neq 0\) and \(\sin((i+1)\theta)=-\sin((m+1-i+1)\theta)\) and thus \(U_i+U_{m+1-i}\) takes the value 0 for all i from 0 to (m+3-1)/2 and if m is odd \(U_{(m+3)/2}\) takes the value 0 also. The symmetry \(i\mapsto j-i\) gives then \(P_{m+1,i}(2\cos(\frac{2t\pi}{m+3}))=0\) for \((m+3)/2< i\leq j\). Hence the function f that associates to the point [m-u-v,u,v] the value \(f([m-u-v,u,v])=P_{u+v,u}(2\cos(\frac{2t\pi}{m+3}))\) constitutes an eigenvector for \(T_m^2\), associated to the eigenvalue

\[2 + 4\cos\left(\frac{2t\pi}{m+3}\right).\]

Moreover, for t=1, the values of the polynomials \(P_{j,i}(2\cos(\frac{2\pi}{m+3}))\) for \(0 \le i \le j \le m\) are positive, because \(\sin(\frac{2\pi}{m+3}) > 0\), \(\sin(\frac{(i+1)2\pi}{m+3}) + \sin(\frac{(j-i+1)2\pi}{m+3}) > 0\) and if j is even \(\sin(\frac{(j/2+1)\pi}{m+3}) > 0\) and thus each sum \((U_i + U_{j-1})\), as well as \(U_{j/2}\) if j is even, takes a positive value. Thus the highest eigenvalue of \(T_m^2\) is \(2 + 4\cos(\frac{2\pi}{m+3})\).

We observe also that the new functions \(f_1\) and \(f_2\) defined by

\[f_1([m-u-v]) = \begin{cases} 0, & \text{if } u = 0 \text{ (mod 3)} \\ f([m-u-v, u, v]), & \text{if } u = 1 \text{ (mod 3)} \\ -f([m-u-v, u, v]), & \text{if } u = 2 \text{ (mod 3)} \end{cases}\]

and

\[f_2([m-u-v]) = \begin{cases} 0, & \text{if } u = 1 \text{ (mod 3)} \\ f([m-u-v, u, v]), & \text{if } u = 2 \text{ (mod 3)} \\ -f([m-u-v, u, v]), & \text{if } u = 0 \text{ (mod 3)} \end{cases}\]

are independent eigenvectors for \(T_m^2\), associated to the eigenvalue

\[-\lambda/2 = -1 - 2\cos\left(\frac{2t\pi}{m+3}\right)\]

unless the eigenvalue is 0.

At this point we may wonder whether \(-\lambda/2 = -1 - 2\cos(\frac{2\pi}{m+3})\) is the smallest eigenvalue of \(T_m^2\). We know already

• \(\mu \le -1 2\cos(\frac{2\pi}{m+3}) = -\lambda/2\),
• \(-1-2\cos(\frac{2\pi}{m+3})\) is the smallest eigenvalue of the three bipartite graphs obtained by removing the vertices in a color class,
• the equality \(\mu = -\lambda/2\) holds for small values of m, indeed Maple checked that from m=1 to m=20.

But the example of the antiprisms on 3p-gons, \(p \ge 3\) shows that one cannot already conclude \(\mu = -\lambda/2\).

Proposition 3.2. The smallest adjacency eigenvalue of \(T_m^2\) is \(-\lambda/2 = -1 - 2\cos(\frac{2\pi}{m+3})\).

Proof. We introduce another family of graphs. The graph G(a,b) has order ab with vertices in \(\mathbb{Z}/a\mathbb{Z} \times [1..b]\) and edges defined by \(\{(x,y),(x+1,y)\}\) for \(x \in \mathbb{Z}/a\mathbb{Z}\) and \(1 \le y \le b\), \(\{(x,y),(x,y+1)\}\) and \(\{(x,y),(x+1,y+1)\}\) for \(x \in \mathbb{Z}/k\mathbb{Z}\) and \(1 \le y < b\).

The eigenvalue of G(a, b) are the reals

\[\phi(t,s) = 2\cos\left(\frac{2t\pi}{a}\right) + 4\cos\left(\frac{t\pi}{a}\right)\cos\left(\frac{s\pi}{b+1}\right)\]

for \(0 \le t \le a-1\) and \(1 \le s \le b\). Corresponding eigenvectors are given by the real and imaginary parts of \((x,y) \mapsto \sin(\frac{sy\pi}{b+1}) \exp(\frac{it\pi(2x-y)}{a})\).

Note that

\[\phi(t,s) = \phi(a-t, b+1-s).\] (1)

It appears that the spectrum of G(3(m+3), m+2) contains 3 times the spectrum of \(T_m^2\). Indeed each eigenvector v of \(T_m^2\) can be extended into an eigenvector f(v) of G(3(m+3), m+2) with the indicated symmetries and null values on the vertices out of the copies of \(T_m^2\) (Figure 5): shifting one step \(\psi: (x,y) \mapsto (x+1,y)\) allows to find 3 linearly independent vectors \(f(v), f(\psi(v)), f(\psi^2(v))\).

However, other eigenvalues of G(3(m+3), m+2), less than the ones of \(T_m^2\) may have high multiplicity, in particular, for m=1 the eigenvalue -2 of G(12,3) has multiplicity 5 and is not in the spectrum \(\{2, (-1)^{[2]}\}\) of \(T_1^2\). For m=2, the multiplicities of 2 and \((-3-\sqrt{5})/2\) are 4 and these numbers are not in the spectrum \(\{1+\sqrt{5}, ((-1+\sqrt{5})/2)^{[2]}, 1-\sqrt{5}, ((-1-\sqrt{5})/2)^{[2]}\}\) of \(T_2^2\). But this phenomenon does not occur for m>2. For \(m\geq 3\) only the values j=1, j=2 and of course m+2, m+1 owing to symmetry (Eq.1)—could provide values smaller than \(-1-2\cos(\frac{2\pi}{m+3})\), since the minimum of \(2\cos 2\theta + 4\cos \theta\cos \alpha\) with \(\theta\) real is obtained with \(2\cos \theta=\cos \alpha\) and its value is \(-3+\sin^2 \alpha\), and \(-1-2\cos(\frac{2\pi}{m+3})=-3+4\sin^2 \alpha\). We note also that \(-1-2\cos(\frac{2\pi}{m+3})=\phi(2m+3,1)=\phi(2m+9,1)=\phi(2m+6,2)\).

Indeed, for \(m \geq 7\) the value j=2 provides only one value smaller than \(-1-2\cos(\frac{2\pi}{m+3})\), namely \(\phi(2m+5,2)\), and for \(m\geq 19, j=2\) provides no value smaller than \(-1-2\cos(\frac{2\pi}{m+3})\). For \(m\geq 7\) the value j=1 provides only 5 values smaller than \(-1-2\cos(\frac{2\pi}{m+3})\), namely \(\phi(t,2)\)

Figure 5. Six copies of \(T_2^2\) in G(15,4) induce 3 copies of the spectrum of \(T_2^2\) in the spectrum of G(15,4)

with \(2m+4 \le t \le 2m+8\). For \(m \ge 19\), we will see that the five values of \(\phi\) are different, and thus are present in the spectrum of G(3m+9,m+2) with multiplicity 2 only and therefore are not eigenvalues of \(T_m^2\).

Computing the five functions

\[3 + \phi(2m + 6 + s, 1) = 2\cos\left(\frac{4\pi}{3} + \frac{2s\pi}{3m + 9}\right) + 4\cos\left(\frac{2\pi}{3} + \frac{s\pi}{3m + 9}\right)\cos\left(\frac{3\pi}{3m + 9}\right),\]

with \(-2 \le s \le 2\) as polynomials of degree at most 5 allows the completion of the proof. For m large, we have in decreasing order

\[\phi(2m+8,1), \phi(2m+4,1), \phi(2m+7,1), \phi(2m+5,1), \phi(2m+6,1).\]

Indeed these polynomials are given in Table 1 (with \(x = \sin(\frac{\pi}{3m+9})\) and \(y = \cos(\frac{\pi}{3m+9})\)).

Figure 6. \(T_2^3\) is not uniquely 4-colorable

Needless to say, for these graphs, since the coarse inequality \(\lambda \leq (1-\chi)\mu\) becomes an equality, the refined inequalities as well as the intermediary inequalities also become equalities.

Table 1. Function \(3 + \phi\) as polynomials in x, y and \(r = \sqrt{3}\)

3.2. Remark about integer simplexes of higher dimension

The equality \(\lambda_1 + (\chi - 1)\lambda_n = 0\) does not hold for m = 2 and d > 2. Indeed, the highest eigenvalue of \(T_2^d\) is \(d - 1 + \sqrt{d^2 + 1}\), and \((d - 1 + \sqrt{d^2 + 1}/d)\) is not an algebraic integer.

The coloration of \(T_m^d\) is not unique in general: Figure 6 shows two colorations of \(T_2^3\) that are not equivalent under color permutation and not even equivalent under color permutation and graph isomorphism. The same possibility of different colorations for \(T_m^d\) occurs at least when there are several non-isomorphic abelian groups of cardinality d+1.

4. Problem

The underlying graphs of examples of Figure 2 are all uniquely 3-colorable graphs on 4 or 5 vertices and even a graph (of size 6) that is not uniquely 3-colorable. Thus the following question is suggested.

Does every uniquely 3-colorable graph admit positive weights such that \(\lambda = -(\chi - 1)\mu\)?

Note that the graph obtained by adding a pendant edge to a triangle (this graph is not uniquely 3-colorable) does not admit such a choice of weights. Indeed, the characteristic polynomial has constant term xy where x and y are the weights of the pendant edge and the one not adjacent to it, but the eigenvalues of the graph should be \(\lambda\), \(-\lambda/2\), and 0, that implies a null constant term.

References

• [1] D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs. Theory and Application, VEB Deutscher Verlag der Wissenschaften (1980).
• [2] C. Godsil. Tools from linear algebra, pp. 1705-1748 in Handbook of Combinatorics. R. L. Graham et al. eds. North Holland (1995).
• [3] W. H. Haemers, Eigenvalue techniques in design and graph theory, Mathematical Centre Tracts 121, Amsterdam (1980).

• [4] A. J. Hoffman, On eigenvalues and colorings of graphs, Graph Theory Appl., Proc. advanced Sem. Wisconsin, Madison 1969, (1970), 79–91.
• [5] R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge University Press (1985).
• [6] R. A. Horn and C. R. Johnson, Topics in matrix analysis, Cambridge University Press (1991).
• [7] V. Nikiforov, On the sum of k largest singular values of graphs and matrices, Linear Algebra and its Applications 435 (2011), 2394-2401.
• [8] D. B. West and M. Ma, Problem 11731 in American Mathematical Monthly 120 (2013), 755.