[Math] Number of vertices in $k$-critical graphs

graph theorygraph-colorings

Let $G=(V,E)$ be a simple, undirected graph. We call it $k$-critical if $\chi(G)=k$ and removing any vertex decreases the chromatic number.

The odd circles $C_{2n+1}$ are all 3-critical. By taking any odd circle and adding a point $\infty$, connecting it to all points in the circle, we get a $4$-critical graph. Similar constructions give rise to the following observation:

If $n \geq k \geq 3$ are positive integers and the difference $n-k$ is even, then there is a an edge set $E$ on $\{1,\ldots, n\}$ such that $(\{1,\ldots,n\},E)$ is a $k$-critical graph.

Does the converse hold, that is: if $(\{1,\ldots,n\},E)$ is a $k$-critical graph, is the difference $n-k$ even?

Best Answer

(I extend my previous comment to this answer.)

I have found (by computer) several examples for that the converse does not hold. The smallest ones are 4-critical graphs on seven vertices. There are (up to isomorphism) exactly seven 4-critical graphs on 7 vertices. One example is the graph $G = (V,E)$ where $V = \{1,2,\dots,7\}$ and $E = \{(1, 3), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 6), (3, 7), (4, 6), (4, 7), (5, 7)\}$, also illustrated in the following figure:

I have also found exactly seven 5-critical graphs on 8 vertices, seven 6-critical graphs (and also a lot of 4-critical graphs) on 9 vertices and seven 7-critical graphs on 10 vertices.

Related Solutions

Graph Theory – Hajos Construction and k-Critical Graphs

Let $G$ and $H$ be $k$-critical graphs and $G +_h H$ be the Hajós construction applied to $G$ and $H$ with respect to $vw \in E(G)$ and $xy \in E(H)$. Since $G$ and $H$ are $k$-critical, $G-vw$ and $H-xy$ both have $(k-1)$-colourings. Permute the colours so that the colour of $v$ is the same as the colour of $x$. Then recolour $w$ with the new colour $k$. This yields a $k$-colouring of $G +_h H$. Towards a contradiction, suppose $c$ is a $(k-1)$-colouring of $G +_h H$. Since $\chi(G)=k$, we must have $c(v)=c(w)$. Similarly, since $\chi(H)=k$, $c(x)=c(y)$. This implies $c(w)=c(y)$, which contradicts that $c$ is a proper colouring. Thus, $\chi(G +_h H)=k$.

It remains to show that for every edge $e$ of $G +_h H$, removing $e$ decreases the chromatic number of $G +_h H$. If $e=wy$, then the previous argument (without the recolouring step) shows that $\chi( (G +_h H) \setminus e) \leq k-1$. Therefore, by symmetry, we may assume that $e \in E(G)$. Since $G$ is $k$-critical, $G \setminus e$ has a $(k-1)$-colouring $c$. Since $H$ is $k$-critical, $H \setminus xy$ has a $(k-1)$-colouring $c'$. Since $\chi(H)=k$, $c'(x)=c'(y)$. Since $vw \in E(G \setminus e)$, $c(v) \neq c(w)$. Therefore, permuting the colours so that $c(v)=c'(x)$ gives a $(k-1)$-colouring of $(G +_h H) \setminus e$.

Critical Graphs – Degeneracy vs Minimal Degree

There is such a graph, provided by the graph6 string

U???????wE?kAgWoAdGpQQ`GdA^?ldgsRW[C~w??

and is uploaded to the House of Graphs.

The graph is critical, as verified by the SageMath code:

a=Graph('U???????wE?kAgWoAdGpQQ`GdA^?ldgsRW[C~w??');
a.chromatic_number() #returns 5
for p in a.vertices():
    b=a.copy()
    b.delete_vertex(p)
    if b.chromatic_number()==5:
        print('The graph is not critical');
        break

(You should not see the message "The graph is not critical".)

The graph has minimum degree $4$ and degeneracy at least $5$:

a.degree(0) #returns 4
a.delete_vertex(0);min(a.degree()) #returns 5

Best Answer

Related Solutions

Graph Theory – Hajos Construction and k-Critical Graphs

Critical Graphs – Degeneracy vs Minimal Degree

Related Question