A Method for Solving Parameter-Bound Problems
Graph-parameter inequalities are most useful when treated as tools with specific jobs. Some give a lower bound on the independence number, some constrain the chromatic number, and others connect clique and independence numbers. A bound can be correct yet weaker than another bound on the same graph; it can also be irrelevant if its hypotheses are not met. This workshop develops a consistent approach: define the graph, compute its parameters carefully, list applicable inequalities, and compare their numerical conclusions.
Throughout, graphs are finite and simple, and the examples have at least one vertex. An independent set is a set of pairwise nonadjacent vertices; its maximum possible size is \(\alpha(G)\). A clique is a set of pairwise adjacent vertices; its maximum possible size is \(\omega(G)\). A proper coloring assigns colors to vertices so adjacent vertices receive different colors; the minimum number of colors is \(\chi(G)\). The degree \(\deg(v)\) is the number of neighbors of \(v\), and \(\Delta(G)\) is the maximum degree.
The spectral radius \(\rho(G)\) is the largest absolute value of an eigenvalue of the adjacency matrix of \(G\). For a corresponding eigenvector \(x\), the eigenvalue equation at vertex \(v\) is \(\lambda x_v=\sum_{u\in N(v)}x_u\). We will use this equation and previously established spectral bounds, without developing adjacency-matrix encoding.
Bounds to Keep at Hand
The first three inequalities follow directly from the definitions. The Caro–Wei inequality and Wilf’s bound are standard results established in the earlier material on graph-parameter bounds; their hypotheses here are finite simple graphs, with \(n\ge1\). For a quick comparison, \(n/\chi(G)\) and \(n/(\Delta(G)+1)\) are lower bounds on \(\alpha(G)\), whereas \(\rho(G)+1\) is an upper bound on \(\chi(G)\). These bounds do not all answer the same question.
Proof. A proper coloring with \(\chi(G)\) colors partitions the \(n\) vertices into \(\chi(G)\) independent color classes. At least one class has size at least their average \(n/\chi(G)\), so \(\alpha(G)\ge n/\chi(G)\). For the maximum-degree bound, repeatedly choose a remaining vertex, add it to a set \(I\), and remove it and all its remaining neighbors. The chosen vertices form an independent set, since choosing a vertex removes every neighbor before another can be chosen. Each choice removes at most \(\Delta(G)+1\) vertices, and the process removes all \(n\) vertices. If it makes \(k\) choices, then \(n\le k(\Delta(G)+1)\), while \(k=|I|\le\alpha(G)\). Thus \(\alpha(G)\ge n/(\Delta(G)+1)\). Finally, every clique of size \(\omega(G)\) requires \(\omega(G)\) distinct colors, so \(\omega(G)\le\chi(G)\). \(\square\)
A useful additional relation is \(\alpha(G)+\omega(G)\le n+1\). To see why, take a maximum clique \(Q\). An independent set can contain at most one vertex of \(Q\), so it contains at most \(n-\omega(G)+1\) vertices in total. This relation can provide an upper bound on \(\alpha(G)\), unlike the three lower bounds above.
Worked Examples: Calculate Before Comparing
Worked Example: A Five-Vertex Path
Let \(G\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\). We calculate the parameters and compare the independence bounds.
The degrees in vertex order are \(1,2,2,2,1\), so \(n=5\), \(|E|=4\), \(\Delta(G)=2\), and \(\delta(G)=1\). The set \(\{1,3,5\}\) is independent. No independent set has more than three vertices: the disjoint edges \(12\) and \(34\) each contribute at most one vertex, and vertex \(5\) contributes at most one more. Hence \(\alpha(G)=3\).
There is an edge, so \(\omega(G)\ge2\); there is no triangle, so \(\omega(G)=2\). Coloring odd-numbered vertices one color and even-numbered vertices another gives a proper 2-coloring, and the edge \(12\) rules out one color. Thus \(\chi(G)=2\).
For Caro–Wei, substitute the five degrees: \(1/(1+1)+1/(2+1)+1/(2+1)+1/(2+1)+1/(1+1)=1/2+1/3+1/3+1/3+1/2=2\). The other independence bounds are \(n/\chi(G)=5/2\) and \(n/(\Delta(G)+1)=5/3\). The strongest numerical lower bound is \(5/2\); since \(\alpha(G)\) is an integer, it implies \(\alpha(G)\ge3\), the exact value. The clique-coloring bounds give \(2=\omega(G)\le\chi(G)\le\rho(G)+1\).
To calculate \(\rho(G)\), the adjacency eigenvalue equations along the path give characteristic-polynomial recurrence \(p_0(x)=1\), \(p_1(x)=x\), and \(p_k(x)=xp_{k-1}(x)-p_{k-2}(x)\). This yields \(p_2=x^2-1\), \(p_3=x^3-2x\), \(p_4=x^4-3x^2+1\), and \(p_5=x^5-4x^3+3x=x(x^2-1)(x^2-3)\). Its roots are \(0,1,-1,\sqrt3,-\sqrt3\), so \(\rho(G)=\sqrt3\). In particular, Wilf gives \(\chi(G)\le1+\sqrt3\), which, because \(\chi(G)\) is an integer, implies \(\chi(G)\le2\). Together with the edge, this confirms \(\chi(G)=2\).
Check: the independent set \(\{1,3,5\}\) has size \(3\), and the bound \(5/2\) rounds up to \(3\). The degree sum is \(1+2+2+2+1=8=2|E|\), as required by the handshake lemma.
Worked Example: A Star and a Warning About Products
Let \(G\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,14,15\}\). Vertex \(1\) is the center, and the other four vertices are leaves.
The degrees are \(4,1,1,1,1\), so \(n=5\), \(\Delta(G)=4\), and \(\delta(G)=1\). The four leaves form an independent set. No independent set can also contain the center, because the center is adjacent to every leaf; therefore \(\alpha(G)=4\). Every edge is a 2-clique and there is no triangle, so \(\omega(G)=2\). Coloring the center one color and all leaves another gives \(\chi(G)=2\), and an edge shows that one color is insufficient.
The coloring bound gives \(\alpha(G)\ge5/2\), and the maximum-degree bound gives \(\alpha(G)\ge5/(4+1)=1\). Caro–Wei gives \(1/(4+1)+4/(1+1)=1/5+4(1/2)=11/5\). Of these, \(5/2\) is strongest, though it is not enough by itself to prove the exact value \(4\). The additional relation gives \(\alpha(G)\le n-\omega(G)+1=5-2+1=4\), which, with the four leaves, determines \(\alpha(G)=4\).
For the spectral radius, let the center coordinate be \(a\) and all four leaf coordinates be \(b\). The eigenvalue equations are \(\lambda a=4b\) and \(\lambda b=a\). For a nonzero eigenvalue these imply \(\lambda^2a=4a\), hence \(\lambda=2\) or \(\lambda=-2\). Vectors with center coordinate zero and leaf coordinates summing to zero give eigenvalue zero; this supplies three independent eigenvectors. Thus the eigenvalues are \(2,-2,0,0,0\), and \(\rho(G)=2\). Wilf gives \(\chi(G)\le3\), while the direct 2-coloring is stronger.
Check: the degree sum is \(4+1+1+1+1=8=2|E|\). Also, \(\alpha(G)+\omega(G)=4+2=6=n+1\), while the proposed product inequality \(\alpha(G)\omega(G)\le n\) would say \(4\cdot2=8\le5\), which is false.
Worked Example: A Triangle with an Isolated Vertex
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,13\}\). Vertex \(4\) is isolated.
The degrees are \(2,2,2,0\), so \(n=4\), \(\Delta(G)=2\), and \(|E|=3\). The set \(\{1,4\}\) is independent. An independent set cannot contain two vertices from the triangle \(\{1,2,3\}\), and it can include vertex \(4\); hence \(\alpha(G)=2\). The triangle is a clique of size \(3\), and vertex \(4\) cannot enlarge it, so \(\omega(G)=3\). The triangle needs three colors, and vertex \(4\) can reuse any of them; therefore \(\chi(G)=3\).
The coloring and maximum-degree bounds give \(\alpha(G)\ge4/3\) and \(\alpha(G)\ge4/(2+1)=4/3\). Caro–Wei gives \(3(1/(2+1))+1/(0+1)=3(1/3)+1=2\), which is exact. The clique lower bound gives \(\chi(G)\ge3\).
The triangle eigenvalue equations have eigenvalues \(2,-1,-1\): the all-ones vector has eigenvalue \(2\), and the two-dimensional subspace of coordinate triples summing to zero has eigenvalue \(-1\). The isolated vertex contributes eigenvalue \(0\). Thus \(\rho(G)=2\), and Wilf gives \(\chi(G)\le2+1=3\). Together with \(\omega(G)=3\le\chi(G)\), this pins down the chromatic number. The isolated vertex matters in the degree sum for Caro–Wei: its term is \(1/(0+1)=1\).
Check: \(3(1/3)+1=2=\alpha(G)\), and \(3=\omega(G)\le\chi(G)=3\le\rho(G)+1=3\). The degree sum is \(2+2+2+0=6=2|E|\).
Choosing the Right Inequality
When given an edge list, keep calculations and deductions separate. First record degrees and obvious structural features, then compute or bound the parameters requested. Only after that compare inequalities. For independence, calculate the three lower bounds \(n/\chi(G)\), \(n/(\Delta(G)+1)\), and \(\sum_v1/(\deg(v)+1)\) when their inputs are known. The largest of these is the strongest of those particular lower bounds. It need not equal \(\alpha(G)\), and a structural argument may do better.
For chromatic number, use \(\omega(G)\le\chi(G)\) as a lower bound and \(\chi(G)\le\rho(G)+1\) as an upper bound. If these agree after accounting for the fact that \(\chi(G)\) is an integer, the chromatic number is determined. If they do not, that gap signals that these inequalities alone do not settle the problem. An upper bound from Wilf is not a lower bound, and an independence lower bound does not automatically identify an independent set of that size unless a construction is also supplied.
A useful final check is to substitute every computed parameter back into the inequality being used. Verify that a lower bound is no larger than the claimed parameter, and an upper bound is no smaller. Also check small structural facts directly: a displayed independent set has no internal edge, a displayed clique has every required edge, and a coloring assigns different colors across every edge. These checks catch many errors that arithmetic alone will not.
Check Your Understanding
For each problem, state which parameters or inequalities you would use and justify the conclusion.
- For \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), compute \(\alpha(G)\), \(\omega(G)\), \(\chi(G)\), \(\Delta(G)\), and the three independence lower bounds.
- For a graph with \(n=8\), \(\chi(G)=4\), and \(\Delta(G)=2\), compare the bounds \(n/\chi(G)\) and \(n/(\Delta(G)+1)\). Which is larger?
- Explain why \(\omega(G)\le\chi(G)\) is a lower bound on the chromatic number, whereas Wilf’s inequality is an upper bound.
- A graph has \(\alpha(G)=5\), \(\omega(G)=3\), and \(n=7\). Check the valid sum inequality and the invalid product inequality.
- Give an example of a graph with an isolated vertex and explain how that vertex contributes to the Caro–Wei sum.