0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ My computer claims that there are (seven) 4-critical graphs on 7 vertices. For example the graph G=(V,E) where V = {1,2,...,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)}. (There are also seven 5-critical graphs on 8 vertices, and seven 6-critical graphs on 9 vertices - but also a lot of 4-critical graphs on 9 vertices). $\endgroup$ – Oliver Krüger Mar 6 '17 at 15:16
  • $\begingroup$ Oh -- that's nice, can you put this as an answer? $\endgroup$ – Dominic van der Zypen Mar 7 '17 at 12:27
  • $\begingroup$ Ok. It has been done. $\endgroup$ – Oliver Krüger Mar 7 '17 at 12:49
3
$\begingroup$

(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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ In case anyone is interested: I posted a list of the (n-3)-critical graphs for n=7,8,9 and 10, in graph6-format, at pastebin.com/R7CZ9pSr $\endgroup$ – Oliver Krüger Mar 7 '17 at 13:00

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.