Graph coloring and the immersion order

Abu-Khzam, Faisal N.; Langston, Micheal A.

Graph coloring and the immersion order

Abu-Khzam, Faisal N.; Langston, Micheal A.

URI: http://hdl.handle.net/10725/5410

URL: https://link.springer.com/chapter/10.1007/3-540-45071-8_40

DOI: http://dx.doi.org/10.1007/3-540-45071-8_40

Date: 2017-03-21

Terms of Use: This item is made available under the terms and conditions applicable to " Conference Paper / Proceeding ", as set forth at: http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php

Abstract:

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.

Citation:

Abu-Khzam, F. N., & Langston, M. A. (2003, July). Graph coloring and the immersion order. In International Computing and Combinatorics Conference (pp. 394-403). Springer Berlin Heidelberg.