Critical Graphs – Degeneracy vs Minimal Degree

co.combinatoricsgraph theory

A finite, simple, undirected graph $G=(V,E)$ is said to be (vertex)-critical if removing any vertex decreases its chromatic number. By $\delta(G)$ we denote the minimum degree of $G$. The degeneracy of $G$ is defined by $$\text{degen}(G) = \max\{\delta(H): H \text{ is an induced subgraph of }G\}.$$
Obviously, for any graph $G$ we have $\delta(G) \leq \text{degen}(G)$.

Question. Is there a vertex-critical graph $G$ such that $\delta(G) < \text{degen}(G)$?

Best Answer

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
Related Question