Immersion Containment and Connectivity in Color-Critical Graphs
Faisal N. Abu-Khzam, Michael A. Langston
Abstract
The relationship between graph coloring and the immersion order is
considered. Vertex connectivity, edge connectivity and related issues
are explored. It is shown that a t-chromatic graph
G contains either an immersed Kt
or an immersed t-chromatic subgraph that is both
4-vertex-connected and t-edge-connected. This gives
supporting evidence of our conjecture that if G requires
at least t colors, then Kt is
immersed in G.
Full Text: PDF PostScript