Graph coloring and the immersion order

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Langston, Micheal A.
dc.date.accessioned 2017-03-21T12:45:17Z
dc.date.available 2017-03-21T12:45:17Z
dc.identifier.isbn 978-3-540-45071-9 en_US
dc.identifier.uri http://hdl.handle.net/10725/5410
dc.description.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. en_US
dc.language.iso en en_US
dc.publisher Springer en_US
dc.title Graph coloring and the immersion order en_US
dc.type Conference Paper / Proceeding en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.identifier.doi http://dx.doi.org/10.1007/3-540-45071-8_40 en_US
dc.identifier.ctation 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. en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.conference.date July 25–28, 2003 en_US
dc.conference.pages 394-403 en_US
dc.conference.place Big Sky, MT, USA en_US
dc.conference.title International Computing and Combinatorics Conference en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url https://link.springer.com/chapter/10.1007/3-540-45071-8_40 en_US
dc.author.affiliation Lebanese American University en_US
dc.title.volume Computing and Combinatorics en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account