Home » Subject » Graph Theory

The chromatic class of the cartesian product of graphs (Solved)

Importance: Low ✭
Author(s):
Subject: Graph Theory
Keywords:
Recomm. for undergrads: no
Posted by: pet_petros
on: December 3rd, 2007
Solved by:
Conjecture   Does there exist graphs $ G $ and $ H $ from Class 1 such that there Cartesian product is from Class 2?

It is known that there are graphs $ G $ and $ H $ which are from Class 2 and their product is from Class 1. Our problem asks the symmetric question. Let us also note that from the classical result of A. Kotzig we imply that there are no regular graphs $ G $ and $ H $ satisfying the conjecture.

add new comment

trivially false

On December 3rd, 2007 mdevos says:

If $ G $ and $ H $ are class 1, then $ G \Box H $ is also class 1. Just choose a $ \Delta(G) $-edge coloring of $ G $ and a $ \Delta(H) $-edge coloring of $ H $, and then assign each edge of $ G \Box H $ the color of the edge it projects to in the appropriate projection map. This gives a proper $ (\Delta(G) + \Delta(H)) $ edge coloring of $ G \Box H $, and $ \Delta(G \Box H) = \Delta(G) + \Delta(H) $.

reply

a more interesting result

On December 3rd, 2007 mdevos says:

a quick google search turned up the following theorem of Mahmoodian:

Theorem   If $ G, H $ are graphs and $ G $ is class 1, then $ G \Box H $ is class 1.

the proof is not difficult and can be found here.

reply

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.