More connectedness of colorings

February 21st, 2007 ~ Posted in: Mathematics

Ok, so I had a thought on how to maybe add edges to the coloring graph mentioned in the previous post so that it would become connected. Namely, in addition to the previous neighbor relation (i\sim j if the colorings differ in exactly one vertex), we could say i \sim j if the partitionings of the graph corresponding to the two colorings are the same, but they assign a different color to each partition. At least this would eliminate the previous counterexample: the graph of 4 colorings on a fully connected 4 vertex graph is connected in this new sense. Does this hold for general graphs and general q-colorings?

This entry was posted on Wednesday, February 21st, 2007 at 9:34 am and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply