TOFT PROBLEM

TOFT PROBLEM. Suppose G is a (k+1)-colorable graph which does not
contain K_(k+1). Does it follow that there are two vertices x and y and
two
k-colorable subgraphs G1 and G2, each containing x and y, such that:
(1) in any k-coloring of G1, x and y receive different colors, and
(2) in any k-coloring of G2, x and y receive the same color.

This problem is true for k=2 and false if k >= 6! Does anyone know the
status
for 2 < k< = 6?

I think that it can be shown that the problem is false for k=3 by
analyzing the
Myceilski Graph.
http://en.wikipedia.org/wiki/Image:Fourth_Mycielski_graph.svg

.

Relevant Pages

  • The Toft Problem
    ... Suppose G is a -colorable graph which does not ... in any k-coloring of G2, x and y receive the same color. ... This makes the Toft problem true for k = 4! ...
    (sci.math)
  • Re: Graph Coloring with the least collision
    ... Or when you don't know for which k a graph is k-coloring, ... the input graph is k colourable), then you could apply that algorithm to ... If the graph was not k-colourable, the colouring will obviously ...
    (comp.theory)
  • Graph Coloring with the least collision
    ... Finding the chromatic number of a graph is a famous NP-Complete ... If we want to color an arbitrary undirected graph G with a fixed ... then is the problem of finding a k-coloring ...
    (comp.theory)