Re: Graph Coloring Problem

|QUESTION: Given a Conflict graph "G" in which the largest clique
| in the graph is of size "k", is the graph "k" colorable?
| (It seems to be true.)


No.


I'm assuming that by a "clique", Peter means a graph (or subgraph of a
larger graph) in which there is an edge between every pair of nodes; I'm
more used to the term "complete graph". (This definition seemed clear
from the earlier posting, but wasn't explicit, so I thought I'd state my
understanding, just to avoid misunderstandings.)


One counter-example is a loop of n nodes and n edges, for any odd n > 3.
This contains no complete subgraph of 3 nodes but can't be coloured with
two colours.




                                                A
                                              / \
                                              E B
                                              | |
                                              D--C


If, say, A is coloured red and B blue, then C is red, D is blue, and E is
red. Oops!


Just as a side note - if the proposition were true, it would be very hard
to prove, as it implies the Four Colour Theorem (since a planar graph
cannot contain a complete subgraph of size 5).
--
Patrick Smith
uunet.ca!frumious!pat
pat%frumious.uucp@uunet.ca
--

Return to the comp.compilers page.
Search the comp.compilers archives again.