Wed, 28 Oct 1992 03:44:28 GMT

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

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.