3
$\begingroup$

Let $n\geq 2$ be an integer and suppose that the finite, simple, undirected graph $G=(V,E)$ is $n$-critical (that is, $\chi(G) = n$, and removing any vertex decreases the chromatic number).

This implies that $G$ is connected, but does $G$ necessarily have a path visiting every vertex exactly once?

$\endgroup$
3
$\begingroup$

Could this be a counterexample for $n=4$? I need to double check it.

$4$-critical graph with no Hamilton path

$\endgroup$
  • $\begingroup$ Yes, this is a counterexample. $\endgroup$ – Gordon Royle Feb 18 '17 at 2:35
2
$\begingroup$

This is some Sage code to check the counterexample posted by user1272680. I can't put this in a comment, so I am putting it as an answer, but the credit should go to user1272680.

g=Graph(21)
g.add_edges([(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(0,10)])
g.add_edges([(1,2),(3,4),(5,6),(7,8),(9,10)])
g.add_edges([(1,11),(2,11),(3,12),(4,12),(5,13),(6,13),(7,14),(8,14),(9,15),(10,15)])
g.add_edges([(11,16),(12,17),(13,18),(14,19),(15,20)])
g.add_edges([(16,17),(17,18),(18,19),(19,20),(20,16)])
print g.chromatic_number()
for e in g.edges():
    h = g.copy()
    h.delete_edge(e)
    print h.chromatic_number()
gd = g.to_directed()
[p for p in gd.all_simple_paths() if len(p) == gd.num_verts()]

First it constructs the graph, checks that it is 4-chromatic, runs through each edge and checks that the edge-deleted graph is 3-chromatic.

Finally it confirms that there are no hamilton paths - Sage apparently only has an "all paths" command for directed graphs, so I just turn the graph into a digraph where each edge becomes two opposite-directed arcs.

$\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.