[Fwd: vertex coloring]

Chuck Biehl (bieh9435@dpnet.net)
Sat, 03 Jan 1998 09:40:30 -0500


This is a multi-part message in MIME format.
--------------C9521C42A86AC50D06DA707F
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Let me throw this out to the entire group. Recap: the conversation
started as applications of graphs coloring, and could be running away :)
The forwarded message could apply to graphs whose edges now form
boundaries which define adjacent surfaces, and for some reason, this
rings a bell, which leads me to pose the following question: Assuming a
planar graph can be drawn with no edge crossings (or a non-planar graph
can be "constructed", eg. in 3D, with no edge crossings), what kind of a
problem situation could you solve by coloring the *regions* such that no
two regions which share an edge are the same color?

Note that I am cc'ing this post to several individuals who I know have
background in graph theory... I apologize for multiple posts.
Happy New Year, too. Looks like it's back to the real world (actually,
the alternate fantasy) on Monday.

-- 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
L. Charles (Chuck) Biehl		(v)302.651.2727
Mathematics, Science & Technology	(f)302.652.1246
The Charter School of Wilmington	http://dimacs.rutgers.edu/~biehl
100 N. DuPont Rd.
Wilmington, DE 19807
--------------C9521C42A86AC50D06DA707F
Content-Type: message/rfc822
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Return-Path: <pcarney@lunar.rutgers.edu> Received: from dimacs.rutgers.edu ([128.6.75.16]) by zeus.dpnet.net (Netscape Mail Server v2.02) with SMTP id AAA391 for <bieh9435@dpnet.net>; Thu, 1 Jan 1998 19:54:27 -0500 Received: from lunar.rutgers.edu (lunar.rutgers.edu [128.6.75.43]) by dimacs.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.12) with ESMTP id TAA12700 for <biehl@dimacs.rutgers.edu>; Thu, 1 Jan 1998 19:51:25 -0500 Received: (from pcarney@localhost) by lunar.rutgers.edu (8.6.12+bestmx+oldruq+newsunq/8.6.12) id TAA03198 for biehl@dimacs.rutgers.edu; Thu, 1 Jan 1998 19:51:25 -0500 Date: Thu, 1 Jan 98 19:51:24 EST From: Patrick Carney <pcarney@lunar.rutgers.edu> To: biehl@dimacs.rutgers.edu Subject: Re: vertex coloring In-Reply-To: Your message of Mon, 22 Dec 1997 10:25:04 -0600 Message-ID: <CMM-RU.1.5.883702284.pcarney@lunar.rutgers.edu>

Hi- I have an idea of what a good subject for the title 3-D graph coloring might be. Since ordinary graph theory is points connected by lines, your student could introduce a new concept of the edges connected by surfaces and then color so no 2 surfaces sharing an edge are the same. Thus a cube would require 3 colors. Interestingly enough on dice, 2 sides would be colored the same if and only if they add up to 7. Hmm, maybew that would be the first theorem of this new 3-D Graph Theory -- at last The Carney Theorem! :-) Anyhow, you might throw it out as a poss9ibility of fitting that title. Hope this si of some help and keeps the young person thinking.

As ever, Pat

--------------C9521C42A86AC50D06DA707F--