Graph Coloring Problem

dahl@ee.umn.edu (peter boardhead dahl)
Sat, 24 Oct 1992 20:49:55 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)
[4 later articles]
| List of all articles for this month |
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.