Re: graph theory

In article <24825490.1177956683619.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxx>,
Mkajuma <mkajumap@xxxxxxxxxxx> wrote:
I'm preparing for my final and have the following question--this is not graded hw nor a test question.
Prove or disprove: If G=F union H then x(G) <= x(F) + x(H) where x(K)
means the chromatic number of K. It seem that the statement is true
but I can't write up a proof.

If F and H are induced graphs of G, then this is easy:


Let u be a coloring for F that uses x(F) colors; let v be a coloring
for H that uses x(H) colors.

Then the coloring for G defined by taking every vertex in F and using
the coloring u, and taking every vertex in H\F and using coloring v.
This will be a coloring of G which uses x(F)+x(H) colors. Thus,
x(G)<=x(F)+x(H).

If the graphs are not induced, then this becomes a bit more
troublesome, but it is not clear to me which way it goes. It could be
false then...


--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org

.