{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:00Z","timestamp":1759638060962},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405344"},{"type":"electronic","value":"9783540450719"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45071-8_40","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T08:04:43Z","timestamp":1193472283000},"page":"394-403","source":"Crossref","is-referenced-by-count":18,"title":["Graph Coloring and the Immersion Order"],"prefix":"10.1007","author":[{"given":"Faisal N.","family":"Abu-Khzam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Langston","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,24]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"B\u00e9la Bollob\u00e1s. Extremal Graph Theory. Academic Press, 1978.","DOI":"10.1007\/978-1-4612-9967-7"},{"key":"40_CR2","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1006\/jagm.1998.0991","volume":"30","author":"H. D. Booth","year":"1999","unstructured":"H. D. Booth, R. Govindan, M. A. Langston, and S. Ramachandramurthi. Sequential and parallel algorithms for K 4 immersion testing. Journal of Algorithms, 30:344\u2013378, 1999.","journal-title":"Journal of Algorithms"},{"key":"40_CR3","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1016\/0095-8956(79)90062-5","volume":"26","author":"Catlin","year":"1979","unstructured":"Catlin. Haj\u00f6s graph-coloring conjecture: variation and counterexamples. JCTB, 26:268\u2013274, 1979.","journal-title":"JCTB"},{"key":"40_CR4","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/jlms\/s1-27.1.85","volume":"27","author":"G. A. Dirac","year":"1952","unstructured":"G. A. Dirac. A property of 4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc., 27:85\u201392, 1952.","journal-title":"J. London Math. Soc."},{"key":"40_CR5","first-page":"71","volume":"13","author":"P. Duchet","year":"1982","unstructured":"P. Duchet and H. Meyniel. On Hadwiger\u2019s number and the stability number. Annals of Discrete Math., 13:71\u201374, 1982.","journal-title":"Annals of Discrete Math."},{"key":"40_CR6","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02579269","volume":"1","author":"P. Erd\u00f6s","year":"1981","unstructured":"P. Erd\u00f6s and S. Fajtlowicz. On the conjecture of Haj\u00f6s. Combinatorica, 1:141\u2013143, 1981.","journal-title":"Combinatorica"},{"key":"40_CR7","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1145\/44483.44491","volume":"35","author":"M. R. Fellows","year":"1988","unstructured":"M. R. Fellows and M. A. Langston. Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM, 35:727\u2013739, 1988.","journal-title":"Journal of the ACM"},{"key":"40_CR8","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1137\/0405010","volume":"5","author":"M. R. Fellows","year":"1992","unstructured":"M. R. Fellows and M. A. Langston. On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM Journal on Discrete Mathematics, 5:117\u2013126, 1992.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"40_CR9","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1016\/S0022-0000(05)80079-0","volume":"49","author":"M. R. Fellows","year":"1994","unstructured":"M. R. Fellows and M. A. Langston. On search, decision and the efficiency of polynomial-time algorithms. Journal of Computer and Systems Sciences, 49:769\u2013779, 1994.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"40_CR10","first-page":"133","volume":"88","author":"H. Hadwiger","year":"1943","unstructured":"H. Hadwiger. \u00dcber eine klassifikation der streckenkomplexe. Vierteljahrsschr. Naturforsch. Ges. Z\u00fcrich, 88:133\u2013142, 1943.","journal-title":"Vierteljahrsschr. Naturforsch. Ges. Z\u00fcrich"},{"key":"40_CR11","first-page":"116","volume":"10","author":"G. Haj\u00f6s","year":"1961","unstructured":"G. Haj\u00f6s. \u00dcber eine konstruktion nicht n-farbbarer graphen. Wiss. Z. Martin Luther Univ. Halle-Wittenberg Math. Naturwiss. Reihe, 10:116\u2013117, 1961.","journal-title":"Wiss. Z. Martin Luther Univ. Halle-Wittenberg Math. Naturwiss. Reihe"},{"key":"40_CR12","doi-asserted-by":"crossref","unstructured":"F. Harary. Graph Theory. Addison-Wesley, 1969.","DOI":"10.21236\/AD0705364"},{"key":"40_CR13","unstructured":"K. Kawarabayashi. On the connectivity of minimal-counterexamples to Hadwiger\u2019s conjecture, to appear."},{"key":"40_CR14","unstructured":"K. Kawarabayashi and B. Toft. Any 7-chromatic graph has K 7 or K 4,4 as a minor. Combinatorica, to appear."},{"key":"40_CR15","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1038\/020275a0","volume":"20","author":"A. B. Kempe","year":"1879","unstructured":"A. B. Kempe. How to color a map with four colours without coloring adjacent districts the same color. Nature, 20:275, 1879.","journal-title":"Nature"},{"key":"40_CR16","first-page":"113","volume":"98","author":"N. G. Kinnersley","year":"1993","unstructured":"N. G. Kinnersley. Immersion order obstruction sets. Congressus Numerantium, 98:113\u2013123, 1993.","journal-title":"Congressus Numerantium"},{"key":"40_CR17","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0012-365X(97)00147-7","volume":"182","author":"M. A. Langston","year":"1998","unstructured":"M. A. Langston and B. C. Plaut. Algorithmic applications of the immersion order. Discrete Mathematics, 182:191\u2013196, 1998.","journal-title":"Discrete Mathematics"},{"key":"40_CR18","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/BF01350657","volume":"178","author":"W. Mader","year":"1968","unstructured":"W. Mader. Homomorphies\u00e4tze f\u00fcr graphen. Math. Ann., 178:154\u2013168, 1968.","journal-title":"Math. Ann."},{"key":"40_CR19","unstructured":"N. Robertson and P.D. Seymour. Graph minors XVI: Wagner\u2019s conjecture. Journal of Combinatorial Theory, Series B, to appear."},{"key":"40_CR20","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF01202354","volume":"13","author":"N. Robertson","year":"1993","unstructured":"N. Robertson, P.D. Seymour, and R. Thomas. Hadwiger\u2019s conjecture for K 6-free graphs. Combinatorica, 13:279\u2013361, 1993.","journal-title":"Combinatorica"},{"key":"40_CR21","unstructured":"T.L. Saaty and P.C. Kainen. The Four-Color Problem. Dover Publications, Inc., 1986."},{"key":"40_CR22","unstructured":"B. Toft. Private communication, 2001."},{"key":"40_CR23","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF01419610","volume":"196","author":"B. Toft","year":"1972","unstructured":"B. Toft. On separating sets of edges in contraction-critical graphs. Math. Ann., 196:129\u2013147, 1972.","journal-title":"Math. Ann."},{"key":"40_CR24","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0012-365X(74)90045-4","volume":"7","author":"B. Toft","year":"1974","unstructured":"B. Toft. On critical subgraphs of colour critical graphs. Discrete Math., 7:377\u2013392, 1974.","journal-title":"Discrete Math."},{"key":"40_CR25","unstructured":"B. Toft. Colouring, stable sets and perfect graphs. In R. Graham, M. Gr\u00f6tschel, and L. Lov\u00e1sz, editors, Handbook of Combinatorics, volume 2, chapter 4, pages 233\u2013288. Elsevier Science B.V., 1995."},{"key":"40_CR26","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF01361181","volume":"153","author":"K. Wagner","year":"1964","unstructured":"K. Wagner. Beweis einer abschw\u00e4chung der Hadwiger-vermutung. Math. Ann., 153:139\u2013141, 1964.","journal-title":"Math. Ann."},{"key":"40_CR27","unstructured":"D. B. West. Introduction to Graph Theory. Prentice Hall, 1996."},{"key":"40_CR28","first-page":"241","volume":"2","author":"H. Whitney","year":"1972","unstructured":"H. Whitney and W.T. Tutte. Kempe chains and the four colour problem. Utilitas Math., 2:241\u2013281, 1972.","journal-title":"Utilitas Math."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45071-8_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T02:09:09Z","timestamp":1556935749000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45071-8_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405344","9783540450719"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-45071-8_40","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}