Chromatic Number After Girth Alteration

From Surviving Vertices to Colors

Deleting vertices can remove short cycles, but it also reduces the number of vertices available to force many colors. To track both effects, compare the order of the graph that remains with an upper bound on the independence number of the original graph. Each color class in a proper coloring is an independent set, so a graph with many surviving vertices and small independent sets must use many colors.

All graphs here are finite and simple. An independent set is a set of vertices no two of which are adjacent. The independence number $\alpha(G)$ is the largest size of an independent set in $G$. A proper coloring assigns colors to vertices so that adjacent vertices receive different colors; the chromatic number $\chi(G)$ is the least number of colors in such a coloring. We use $\alpha(G)=0$ and $\chi(G)=0$ for the graph with no vertices.

Definition: For a vertex set $X\subseteq V(G)$, the graph remaining after deleting $X$ is the induced subgraph $H=G[V(G)\setminus X]$. It has all vertices outside $X$ and all edges of $G$ whose endpoints are both outside $X$.

Deleting vertices cannot create edges among the vertices that remain. Consequently, every independent set of $H$ is also an independent set of $G$. In particular, $\alpha(H)\leq\alpha(G)$. This simple comparison is the key to retaining a chromatic lower bound.

The Chromatic Lower Bound After Deletion

Theorem: Let $G$ be a finite graph, let $X\subseteq V(G)$, and let $H=G[V(G)\setminus X]$. If $a$ is a positive integer and $\alpha(G)\leq a$, then $$ \chi(H)\geq \left\lceil\frac{|V(G)|-|X|}{a}\right\rceil. $$

Proof. Write $n=|V(G)|$ and $n'=|V(H)|=n-|X|$. First suppose $n'>0$, and consider any proper coloring of $H$ using $k$ colors. The vertices assigned each one color form an independent set in $H$, and hence in $G$. Each color class therefore has at most $\alpha(G)\leq a$ vertices. The $k$ color classes partition the $n'$ vertices, so $n'\leq ka$. Since $a>0$, division gives $k\geq n'/a$. As $k$ is an integer, $k\geq\lceil n'/a\rceil$. This holds for every proper coloring, including one using $\chi(H)$ colors. If $n'=0$, then $\chi(H)=0$ and the right-hand side is $\lceil0/a\rceil=0$, so the inequality also holds. $\square$

The ceiling matters: a chromatic number is an integer. A useful consequence is that if at most $q$ vertices are deleted, then $$ \chi(H)\geq \left\lceil\frac{n-q}{a}\right\rceil $$ whenever $\alpha(G)\leq a$. This follows because $|X|\leq q$ gives $n-|X|\geq n-q$, and the ceiling function is nondecreasing. When $n-q$ is negative, this estimate is still true but may give no useful positive lower bound.

Worked Example: Deleting a Vertex from a 5-Cycle

Let $G$ have vertex set $\{1,2,3,4,5\}$ and edge set $\{12,23,34,45,51\}$. Delete $X=\{1\}$, leaving the induced subgraph $H$ on $\{2,3,4,5\}$.

The remaining edges are $23,34,45$, so $H$ is the path $2,3,4,5$ and has $n'=5-1=4$ vertices. To find $\alpha(G)$, note that between any two chosen vertices of the 5-cycle there must be an unchosen vertex if the chosen vertices are to be independent. Three chosen vertices would therefore require at least three unchosen vertices, more than the two available. Thus $\alpha(G)\leq2$; the set $\{1,3\}$ is independent, so $\alpha(G)=2$.

Apply the theorem with $a=2$: $$ \chi(H)\geq\left\lceil\frac{4}{2}\right\rceil =\lceil2\rceil=2. $$ The alternating coloring $2,4$ with one color and $3,5$ with another is proper, so $\chi(H)\leq2$. Hence $\chi(H)=2$, agreeing with the lower bound.

Check: the three edges $23,34,45$ each join vertices in different color classes. The graph left after deletion has no cycle, as required if the aim is to remove the original 5-cycle.

Applying the Bound to Short-Cycle Deletion

A cycle is a closed sequence of at least three edges whose vertices, apart from the repeated start and end, are distinct. For an integer $g\geq3$, call a cycle short here if its length is at most $g$. A graph has no cycles of length at most $g$ if none of its subgraphs is such a cycle. Deleting a vertex from each short cycle provides a direct way to remove all these cycles.

Proposition: Let $G$ have $n$ vertices and $\alpha(G)\leq a$, where $a\geq1$. Suppose $G$ has $C$ cycles of length at most $g$, for some integer $g\geq3$. There is a set $X$ of at most $C$ vertices such that $H=G[V(G)\setminus X]$ has no cycle of length at most $g$, and $$ \chi(H)\geq\left\lceil\frac{n-|X|}{a}\right\rceil. $$ In particular, if $C\leq n$, then $\chi(H)\geq\left\lceil\frac{n-C}{a}\right\rceil$.

Proof. The graph is finite, so it has only finitely many cycles of length at most $g$. List these cycles. From each cycle in the list choose one of its vertices, and let $X$ be the set of all chosen vertices. If two cycles yield the same chosen vertex, that vertex appears only once in $X$, so $|X|\leq C$. Any cycle of length at most $g$ remaining in the induced subgraph $H$ would also have been a cycle in the original list. But its chosen vertex belongs to $X$, so it cannot remain in $H$. Thus $H$ has no cycle of length at most $g$. The theorem gives $\chi(H)\geq\lceil(n-|X|)/a\rceil$. If $C\leq n$, then $n-|X|\geq n-C$; monotonicity of the ceiling gives the stated particular bound. $\square$

This proposition separates the two quantities that an alteration argument must control: how many vertices are lost, and how large an independent set can be. If $C\leq n$ and $n-C>(r-1)a$ for an integer $r\geq1$, then $(n-C)/a>r-1$, so $\lceil(n-C)/a\rceil\geq r$. Consequently, the graph with no cycles of length at most $g$ has chromatic number at least $r$. This is a sufficient numerical condition, not a claim that every deletion set realizes the strongest possible bound.

Worked Example: Removing the Triangles from Two Components

Let $G$ have vertex set $\{1,2,3,4,5,6\}$ and edge set $\{12,23,31,45,56,64\}$. Thus $G$ consists of two disjoint triangles. Its only cycles are those two triangles: within each three-vertex component all three edges are present, and there are no edges between the components. Hence the number $C$ of cycles of length at most $3$ is $2$.

An independent set can contain at most one vertex from each triangle, so $\alpha(G)\leq2$. Choosing one vertex from each triangle gives an independent set of size $2$, and therefore $\alpha(G)=2$. Choose $X=\{1,4\}$, one vertex from each triangle. The remaining graph $H$ has vertices $\{2,3,5,6\}$ and edges $\{23,56\}$. It has $n'=6-2=4$ vertices and contains no cycle.

With $a=2$, the theorem gives $$ \chi(H)\geq\left\lceil\frac{4}{2}\right\rceil=2. $$ The two edges require different colors at their endpoints, and assigning one color to $\{2,5\}$ and a second to $\{3,6\}$ is proper. Thus $\chi(H)=2$. Independently, the count of short cycles gives the same lower bound: $\lceil(n-C)/a\rceil=\lceil(6-2)/2\rceil=2$.

Why the Original Order Cannot Be Reused

The bound depends on the number of vertices that actually remain. A vertex removed to break a cycle is no longer part of any color class of $H$. Keeping $n$ in the numerator after deletion can produce a false conclusion, even when the independence-number estimate is correct.

Worked Example: A False Bound from the Deleted Vertices

Let $G$ be the complete graph on $\{1,2,3,4,5\}$, with edge set consisting of all ten pairs of distinct vertices. Since every two vertices are adjacent, $\alpha(G)=1$. Delete $X=\{1,2,3\}$. The remaining graph $H$ has vertex set $\{4,5\}$ and edge set $\{45\}$, so it has $n'=5-3=2$ vertices and $\chi(H)=2$.

A mistaken calculation keeps the original order and claims $$ \chi(H)\geq\left\lceil\frac{5}{1}\right\rceil=5. $$ This contradicts the explicit two-coloring of $H$, so the calculation cannot be valid. The theorem uses the surviving order instead: $$ \chi(H)\geq\left\lceil\frac{5-3}{1}\right\rceil =\lceil2\rceil=2. $$ This is correct and tight. In this example the deletion also removes every triangle, since only two vertices remain.

The general lesson is to keep the quantities aligned: use an upper bound on independent-set size that applies to the original graph, and use the order of the graph after deletion. The former transfers to the induced subgraph; the latter records exactly how many vertices still need colors. Short-cycle deletion then affects the chromatic lower bound through its vertex cost, while the independence estimate supplies the color-class limit.

Check Your Understanding

For each question, identify the surviving order before applying a chromatic lower bound.

If $\alpha(G)\leq4$ and $7$ vertices are deleted from a $31$-vertex graph, what lower bound does the theorem give for the chromatic number of the induced subgraph that remains?
Explain why every independent set of $G[V(G)\setminus X]$ is also an independent set of $G$.
A graph has $\alpha(G)\leq3$ and at most $5$ cycles of length at most $4$. What sufficient condition on $n=|V(G)|$ guarantees that deleting one vertex from each such cycle leaves a graph with chromatic number at least $4$?
Why does selecting one vertex from each cycle of length at most $g$ ensure that the induced graph on the remaining vertices has no such cycle?
In the complete-graph example, why does substituting the original order into the theorem give an invalid bound after three vertices are deleted?

Chromatic Number After Girth Alteration

What You'll Learn