# Re: Graph Coloring Problem

## pat%frumious.uucp@uunet.ca (Patrick Smith)Wed, 28 Oct 1992 03:44:28 GMT

From comp.compilers

Related articles
Graph Coloring Problem dahl@ee.umn.edu (1992-10-24)
Re: Graph Coloring Problem pugh@cs.umd.edu (1992-10-27)
Re: Graph Coloring Problem jrbd@craycos.com (1992-10-27)
Re: Graph Coloring Problem pat%frumious.uucp@uunet.ca (1992-10-28)
Re: Graph Coloring Problem Richter@lrz.lrz-muenchen.dbp.de (1992-10-28)
Re: Graph Coloring Problem cliffc@rice.edu (1992-10-28)
Re: Graph Coloring Problem moss@cs.umass.edu (1992-10-28)
Re: Graph Coloring Problem preston@cs.rice.edu (1992-10-30)
Re: Graph Coloring Problem sgall+@CS.CMU.EDU (1992-10-31)
Re: Graph Coloring Problem kuzemcha@tartan.com (1992-11-06)
| List of all articles for this month |

 Newsgroups: comp.compilers From: pat%frumious.uucp@uunet.ca (Patrick Smith) Organization: Compilers Central Date: Wed, 28 Oct 1992 03:44:28 GMT References: 92-10-093 Keywords: theory

|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
--

Post a followup to this message