MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Who can help me?

  • To: mathgroup at
  • Subject: [mg26818] Re: [mg26778] Who can help me?
  • From: Jacqueline Zizi <jazi at>
  • Date: Thu, 25 Jan 2001 01:13:03 -0500 (EST)
  • References: <001801c084d2$ac9023e0$a7e3e994@dqb2301>
  • Sender: owner-wri-mathgroup at

Thanks to everybody that answers me. Tomas Garza points out very deep important
facts (from my intuitive point of view).

The Tomas Garza  property (see below) looks indeed very important and might
help to solve an old well known open problem in this field.

Here is now some explanations about this polynomial. Coloring a graph G with
n-vertices means coloring the vertices such as deux vertices linked can't take
the same color. The function x colors -> number of ways of coloring G with x
colors, is shown to be a polynomial and it is called the chromatic polynomial
of G. Notation p(x). For example for a complete graph p(x)= x(x-1)... (x-n+1).

The 4th- color problem is: the chromatic polynomial of every planar graph has
an integer value X less or equal 4, such that p(X)>0.  For non planar graphs,
this first value such that p(X) >0  can be higher. For example for a complete
graph this number is n; Notice that indeed in this special case, for 1 to n-1
it is 0.

There is 2 well known ways for prooving of the 4th-color problem. The one done
and the other one by chromatic polynomials. People gave up facing large
polynomials and the NP-Hard difficulty of computing the polynomials.
Nevertheless, properties of these invariants and some more general invariants
generalizations of it are promising in different areas.

Now one interesting graph configuration for lots of confluent reasons from
different areas (group's theory, chemistry for example), is the truncated
icosahedron. Hall and his students took more than 15 years to find the
corresponding chromatic polynomial. This is our beast.

If still reading this, notice that there is a more important fact :  this Tomas
Garza property is also true, in more general situations. Indeed I'm just
looking at this and  if we believe Mathematica,  this is glorious!


Nevertheless my main questions remains:

1) How could I check the results given by Mathematica?

2) If people trust the proof of the 4th color problem, why should not they
trust this too?

3) Is there a mean to proove that in a mathematical way?

Jacqueline Zizi

Tomas Garza wrote:

> Further comments to my previous message. Other than the numerical problem, I
> found an interesting (or so it seems to me) fact. I haven't the faintest
> idea what your original problem is about, but the polynomial has the
> property that if you take the first j terms, then its numerical value for
> x-> 2 + 2 Cos [2 Pi / 7] is the negative of the numerical value of the last
> 32 - j terms for that same x, for j = 1 to 31.

  • Prev by Date: RE: [Q] symbolic SVD?
  • Next by Date: [no subject]
  • Previous by thread: Re: Who can help me?
  • Next by thread: Re: Who can help me?