Skip to content Skip to main navigation Report an accessibility issue

EECS Publication

Graph Coloring and the Immersion Order

Faisal N. Abu-Khzam and Michael A. Langston

The relationship between graph coloring and the immersion order is considered. Vertex connectivity, edge connectivity and related issues are explored. These lead to the conjecture that, if G requires at least t colors, then G must have immersed within it Kt, the complete graph on t vertices. Evidence in support of such a proposition is presented. For each fixed value of t, there can be only a finite number of minimal counterexamples. These counterexamples are characterized based on Kempe chains, connectivity, cutsets and degree bounds. It is proved that minimal counterexamples must, if any exist, be both 4-vertex-connected and t-edge-connected.

Published  2002-12-01 05:00:00  as  ut-cs-02-494 (ID:240)


« Back to Listing