4
$\begingroup$

I'm looking to construct the smallest possible graph that forces an $N$ coloring. I am measuring graph size by the number of edges.

There's an easy upper bound: A complete graph has $\frac {n(n-1)}{2}$ edges, and requires an $N$ coloring.

Furthermore, if you take a complete graph, and remove one of the edges, then you take the two nodes that are now disconnected and color one of them the color of the other. Therefore, the smallest graph with $N$ nodes and an $N$ coloring is the complete graph.

However, I'm not convinced that there isn't a graph with more than $N$ nodes but fewer than $\frac {n(n-1)}{2}$ edges that still requires a coloring of $N$.

$\endgroup$
3
$\begingroup$

Let $G=(V,E)$ be any graph with chromatic number $n.$ Consider a proper coloring of $G$ with colors $c_1,c_2,\dots,c_n.$ For each pair $i,j$ with $1\le i\lt j\le n$ there must be an edge $e_{i,j}\in E$ which joins a vertex of color $c_i$ to a vertex of color $c_j;$ if there were no such edge, then by recoloring all vertices of color $c_i$ with color $c_j$ we would obtain a proper coloring of $G$ with $n-1$ colors. Thus $G$ has at least $\frac{n(n-1)}2$ edges.

$\endgroup$
2
$\begingroup$

Yes, any graph that requires $n$ colors must have at least $n(n-1)/2$ edges.

Suppose to the contrary there exists a graph with $e<n(n-1)/2$ edges that forces an $n$-coloring, i.e. cannot be $(n-1)$-colored. Choose such a graph $G$ with the fewest possible edges.

Now, note that the average degree of a vertex is $d=2e/v$, where $v$ is the number of vertices. Note that $v\geq n$ or else we could just assign each vertex its own color. Since $e<n(n-1)/2$, this implies that $d<n-1$. Not every vertex can have above-average degree, so some vertex has degree at most $n-2$; call it $v_0$.

But, then if we delete $v_0$ from $G$, the resulting graph $G'$ is still not $(n-1)$-colorable. That's because it if it were, we could extend its coloring to $G$ by choosing a color for $v_0$ different those of its $n-2$ or fewer neighbors. But $G'$ has fewer edges than $G$, contradicting $G$'s minimality.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.