Fri, 30 Oct 1992 01:16:06 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,comp.theory |

From: | preston@cs.rice.edu (Preston Briggs) |

Organization: | Rice University, Houston |

Date: | Fri, 30 Oct 1992 01:16:06 GMT |

References: | 92-10-093 |

Keywords: | theory |

dahl@ee.umn.edu (peter boardhead dahl) writes:

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

Hi Peter,

I think not. Here's a counter-example.

Look at a string of 4-cliques. I'll draw the basic clique like this

0 - 2

| X |

1 - 3

that is, four vertices: 0, 1, 2, 3

and 6 edges: 0-1, 0-2, 0-3, 1-3, 1-2, 2-3

The string would look like

0 - 2 - 4 - 6 - 8

| X | X | X | X |

1 - 3 - 5 - 7 - 9

Assigning colors (say, a, b, c, and d), we get

a - c - a - c - a

| X | X | X | X |

b - d - b - d - b

which is fine. Now suppose we connect the ends of our string,

creating a new clique, with the edges

0-8, 1-8, 0-9, 1-9

The resulting graph can't be colored in only four colors;

but the largest clique still has only 4 vertices.

Here's the smallest counterexample.

Consider a pentagon.

The largest clique is 2, but it requires 3 colors.

1 - 2

| |

2 1

\ /

3

Of course, it's easy to make larger cases.

All simple cycles with an odd number of vertices require 3 colors,

and in all cases with more than 3 vertices, the largest clique is 2.

Preston Briggs

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.