Sat, 24 Oct 1992 20:49:55 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) |

[4 later articles] |

Newsgroups: | comp.compilers,comp.theory |

From: | dahl@ee.umn.edu (peter boardhead dahl) |

Organization: | University of Minnesota, Minneapolis, EE dept. |

Date: | Sat, 24 Oct 1992 20:49:55 GMT |

Keywords: | theory, question |

We need help with a Graph Coloring Problem!

Facts: A *clique* of size "k" is "k" colorable.

----- -----

| A | ---- | B | This is a clique of size 4.

----- -----

| \ / | => This graph is 4 colorable.

| \/ |

| /\ |

| / \ |

----- -----

| C | ---- | D |

----- -----

Observation: A general Conflict graph is an interconnection of cliques.

The Conflict Graph "G" below is made up of 6 interconnected 3-cliques.

(All the cliques don't have to be the same size, they just are in this

example.) Also the largest clique in this graph is of size "3".

Cliques:

1) A-B-D 4) C-D-F

2) A-C-D 5) D-E-F

3) B-D-E 6) D-F-G

Note: Any clique included in a larger clique is counted as part of the

larger. ex: The 2-clique A-C is counted as part of the 3-clique A-C-D.

Graph: "G"

----- -----

| A | ----- | B |

/ ----- ----- \

/ \ / \

/ \ / \

/ \ / \

/ \ / \

----- ----- -----

| C | ---------- | D | ---------- | E |

----- ----- -----

\ / \ /

\ / \ /

\ / \ /

\ / \ /

\ ----- ----- /

| F | ----- | G |

----- -----

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

ex: In the graph "G" above, the largest clique is of size 3 and it's

also 3 colorable. ( works in this case, how about others? )

--

Peter Bergner (bergner@ee.umn.edu)

Peter Dahl (dahl@ee.umn.edu)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.