Open Problem Garden - Double-critical graph conjecture - Comments

Statement needs connected assumption (re: Double-critical graph conjecture)

Anonymous — Mon, 30 Nov 2009 21:30:37 +0100

G needs to be assumed connected in the statement. Otherwise the disjoint union of K_k and a vertex (say) would be a counterexample.

missing connectivity condition (re: Double-critical graph conjecture)

Anonymous — Fri, 29 May 2009 01:48:07 +0200

As it is now the conjecture is false -- take the disjoint union of a clique and a vertex. Just need to add "connected" to the definition of doubly critical.

Double-critical graph conjecture

DFR — Sun, 18 Jan 2009 06:27:51 +0100

Author(s): Erdos; Lovasz

Subject: Graph Theory » Coloring » Vertex coloring

A connected simple graph is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.

Conjecture is the only -chromatic double-critical graph