|Graph Coloring Problem email@example.com (1992-10-24)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-10-27)|
|Re: Graph Coloring Problem email@example.com (1992-10-27)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-10-28)|
|Re: Graph Coloring Problem Richter@lrz.lrz-muenchen.dbp.de (1992-10-28)|
|Re: Graph Coloring Problem email@example.com (1992-10-28)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-10-28)|
|Re: Graph Coloring Problem email@example.com (1992-10-30)|
|Re: Graph Coloring Problem sgall+@CS.CMU.EDU (1992-10-31)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-11-06)|
|From:||email@example.com (Patrick Smith)|
|Date:||Wed, 28 Oct 1992 03:44:28 GMT|
|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.)
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
If, say, A is coloured red and B blue, then C is red, D is blue, and E is
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).
Return to the
Search the comp.compilers archives again.