{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:42:34Z","timestamp":1750308154515,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":75,"publisher":"ACM","license":[{"start":{"date-parts":[[2006,5,21]],"date-time":"2006-05-21T00:00:00Z","timestamp":1148169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2006,5,21]]},"DOI":"10.1145\/1132516.1132576","type":"proceedings-article","created":{"date-parts":[[2006,7,24]],"date-time":"2006-07-24T16:53:01Z","timestamp":1153759981000},"page":"401-416","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs"],"prefix":"10.1145","author":[{"given":"Ken-ichi","family":"Kawarabayashi","sequence":"first","affiliation":[{"name":"Tohoku University, Sendai, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[{"name":"University of Ljubljana, Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,5,21]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1256049011"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1256049012"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90646-W"},{"key":"e_1_3_2_1_5_1","first-page":"307","volume-title":"Thirty-Second Annual Symposium (G. Davison, ed.), AGIFORS (Airline Group of the international Federation of Operational Research)","author":"Biro M.","year":"1993","unstructured":"M. Biro , M. Hujter , and Z. Tuza . Cross fertilisation of graph theory and aircraft maintenace scheduling . In Thirty-Second Annual Symposium (G. Davison, ed.), AGIFORS (Airline Group of the international Federation of Operational Research) , pages 307 -- 317 , 1993 .]] M. Biro, M. Hujter, and Z. Tuza. Cross fertilisation of graph theory and aircraft maintenace scheduling. In Thirty-Second Annual Symposium (G. Davison, ed.), AGIFORS (Airline Group of the international Federation of Operational Research), pages 307--317, 1993.]]"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00190-1"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90009-4"},{"key":"e_1_3_2_1_9_1","unstructured":"T. Bohme K. Kawarabayashi J. Maharry and B. Mohar. Linear connectivity forces large complete bipartite minors. To appear in J. Combin. Theory Ser B.]]  T. Bohme K. Kawarabayashi J. Maharry and B. Mohar. Linear connectivity forces large complete bipartite minors. To appear in J. Combin. Theory Ser B.]]"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261316"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90049-3"},{"key":"e_1_3_2_1_12_1","first-page":"551","volume-title":"Proceedings of the 43th Annual Symposium on Foundations of Computer Science (FOCS'02)","author":"Charikar M.","year":"2002","unstructured":"M. Charikar and A. Sahai . Dimension reduction in the l1 norm . In Proceedings of the 43th Annual Symposium on Foundations of Computer Science (FOCS'02) , pages 551 -- 560 , 2002 .]] M. Charikar and A. Sahai. Dimension reduction in the l1 norm. In Proceedings of the 43th Annual Symposium on Foundations of Computer Science (FOCS'02), pages 551--560, 2002.]]"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(71)90065-7"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-44.1.612"},{"key":"e_1_3_2_1_15_1","first-page":"527","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03)","author":"Chekuri C.","year":"2003","unstructured":"C. Chekuri , A. Gupta , I. Newman , Y. Rabinovich , and S. Alistair . Embedding k-outerplanar graphs into '1 . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03) , pages 527 -- 536 , 2003 .]] C. Chekuri, A. Gupta, I. Newman, Y. Rabinovich, and S. Alistair. Embedding k-outerplanar graphs into '1. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03), pages 527--536, 2003.]]"},{"key":"e_1_3_2_1_16_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1007\/BFb0015449","volume-title":"Proc. 6th Internat. Symp. on Algorithms and Computation","author":"Chen Z.-Z.","year":"1995","unstructured":"Z.-Z. Chen . NC algorithms for partitioning sparse graphs into induced forests with an application . In Proc. 6th Internat. Symp. on Algorithms and Computation , Lecture Notes in Computer Science , Vol. 1004 , Springer , Berlin , pages 428 -- 437 , 1995 .]] Z.-Z. Chen. NC algorithms for partitioning sparse graphs into induced forests with an application. In Proc. 6th Internat. Symp. on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 1004, Springer, Berlin, pages 428--437, 1995.]]"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00254-5"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(96)00089-3"},{"key":"e_1_3_2_1_19_1","volume-title":"North-Holland","author":"Cunningham W.","year":"1978","unstructured":"W. Cunningham and A. Marsh . A primal algorithm for optimum matching. In Polyhedral Combinatorics, (dedicated to the memory of D. R. Fulkerson), Eds: M. L. Balinski and A. J. Hoffman, Math. Programming Sud. No. 8 , North-Holland , Amsterdam, pages 60--72 , 1978 .]] W. Cunningham and A. Marsh. A primal algorithm for optimum matching. In Polyhedral Combinatorics, (dedicated to the memory of D. R. Fulkerson), Eds: M. L. Balinski and A. J. Hoffman, Math. Programming Sud. No. 8, North-Holland, Amsterdam, pages 60--72, 1978.]]"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.14"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1962"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-27.1.85"},{"key":"e_1_3_2_1_23_1","first-page":"125","volume-title":"Proc. West-Coast conference on Combinatorics Graph Theory and Computing, Arcata Califonia, Congressus Numerantium","author":"Erdos P.","year":"1979","unstructured":"P. Erdos , Rubin, and Taylor. Choosability in graphs . In Proc. West-Coast conference on Combinatorics Graph Theory and Computing, Arcata Califonia, Congressus Numerantium , volume XXVI , pages 125 -- 157 , 1979 .]] P. Erdos, Rubin, and Taylor. Choosability in graphs. In Proc. West-Coast conference on Combinatorics Graph Theory and Computing, Arcata Califonia, Congressus Numerantium, volume XXVI, pages 125--157, 1979.]]"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/44483.44491"},{"key":"e_1_3_2_1_26_1","volume-title":"Implementation of algorithms for maximum matching on non-bipartite graphs. Ph","author":"Gabow H.","year":"1973","unstructured":"H. Gabow . Implementation of algorithms for maximum matching on non-bipartite graphs. Ph . D. Stanford University , Dep . Comput., 1973 .]] H. Gabow. Implementation of algorithms for maximum matching on non-bipartite graphs. Ph . D. Stanford University, Dep. Comput., 1973.]]"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382762"},{"key":"e_1_3_2_1_28_1","unstructured":"J. Geelen B. Gerards L. Goddyn B. Reed P. Seymour and A. Vetta. The odd case of Hadwiger's conjecture. Submitted.]]  J. Geelen B. Gerards L. Goddyn B. Reed P. Seymour and A. Vetta. The odd case of Hadwiger's conjecture. Submitted.]]"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2002.2128"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90166-Y"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(81)90020-1"},{"key":"e_1_3_2_1_33_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/3-540-69346-7_2","volume-title":"Integer Programming and Combinatorial optimizaition, Proceedings, 6th IPCO conference","author":"Guenin B.","year":"1998","unstructured":"B. Guenin . A characterization of weakly bipartite graphs . In Integer Programming and Combinatorial optimizaition, Proceedings, 6th IPCO conference , Houston, Texas , 1998 , (R.E. Bixby et al., Eds), Lecture Notes in Computer Science , Springer-Verlag , Berlin, volume 1412 , pages 9 -- 22 .]] B. Guenin. A characterization of weakly bipartite graphs. In Integer Programming and Combinatorial optimizaition, Proceedings, 6th IPCO conference, Houston, Texas, 1998, (R.E. Bixby et al., Eds), Lecture Notes in Computer Science, Springer-Verlag, Berlin, volume 1412, pages 9--22.]]"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2051"},{"key":"e_1_3_2_1_35_1","volume-title":"Talk at Oberwolfach on graph theory","author":"Guenin B.","year":"2005","unstructured":"B. Guenin . Talk at Oberwolfach on graph theory . Jan. 2005 .]] B. Guenin. Talk at Oberwolfach on graph theory. Jan. 2005.]]"},{"key":"e_1_3_2_1_36_1","first-page":"399","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS'99)","author":"Gupta A.","year":"1999","unstructured":"A. Gupta , I. Newman , Y. Rabinovich , and S. Alistair . Cuts, trees and '1-embeddings of graphs . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS'99) , pages 399 -- 409 , 1999 .]] A. Gupta, I. Newman, Y. Rabinovich, and S. Alistair. Cuts, trees and '1-embeddings of graphs. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS'99), pages 399--409, 1999.]]"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00104-5"},{"key":"e_1_3_2_1_38_1","first-page":"133","volume-title":"Ges. Zurich","volume":"88","author":"Hadwiger H.","year":"1943","unstructured":"H. Hadwiger . \u00dcber eine Klassifikation der Streckenkomplexe. In Vierteljahrsschr. naturforsch . Ges. Zurich , volume 88 , pages 133 -- 142 , 1943 .]] H. Hadwiger. \u00dcber eine Klassifikation der Streckenkomplexe. In Vierteljahrsschr. naturforsch. Ges. Zurich, volume 88, pages 133--142, 1943.]]"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1055"},{"key":"e_1_3_2_1_41_1","volume-title":"Graph Coloring Problems","author":"Jensen T. R.","year":"1995","unstructured":"T. R. Jensen and B. Toft . Graph Coloring Problems . Wiley-Interscience , 1995 .]] T. R. Jensen and B. Toft. Graph Coloring Problems. Wiley-Interscience, 1995.]]"},{"key":"e_1_3_2_1_42_1","unstructured":"K. Kawarabayashi. Linkage problem and its application to hadwiger's conjecture. preprint.]]  K. Kawarabayashi. Linkage problem and its application to hadwiger's conjecture. preprint.]]"},{"key":"e_1_3_2_1_43_1","unstructured":"K. Kawarabayashi. Minors in 7-chromatic graphs. Preprint.]]  K. Kawarabayashi. Minors in 7-chromatic graphs. Preprint.]]"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.04.004"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007479"},{"key":"e_1_3_2_1_46_1","unstructured":"K. Kawarabayashi and B. Mohar. Algorithmic aspects of Hadwiger's conjecture. Submitted.]]  K. Kawarabayashi and B. Mohar. Algorithmic aspects of Hadwiger's conjecture. Submitted.]]"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.11.002"},{"key":"e_1_3_2_1_48_1","unstructured":"K. Kawarabayashi and B. Reed. Highly parity linked graphs. To appear in Combinatorica.]]  K. Kawarabayashi and B. Reed. Highly parity linked graphs. To appear in Combinatorica.]]"},{"key":"e_1_3_2_1_49_1","unstructured":"K. Kawarabayashi and Z. Song. Some remarks on the odd hadwiger's conjecture. To appear in Combinatorica.]]  K. Kawarabayashi and Z. Song. Some remarks on the odd hadwiger's conjecture. To appear in Combinatorica.]]"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0019-1"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.08.001"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167261"},{"key":"e_1_3_2_1_53_1","first-page":"37","article-title":"The minimum Hadwiger number for graphs with a given mean degree of vertices (in Russian)","volume":"38","author":"Kostochka A.","year":"1982","unstructured":"A. Kostochka . The minimum Hadwiger number for graphs with a given mean degree of vertices (in Russian) . Metody Diskret. Analiz. , 38 : 37 -- 58 , 1982 .]] A. Kostochka. The minimum Hadwiger number for graphs with a given mean degree of vertices (in Russian). Metody Diskret. Analiz., 38:37--58, 1982.]]","journal-title":"Metody Diskret. Analiz."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579141"},{"key":"e_1_3_2_1_55_1","unstructured":"E. Lawler. Combinatorial optimization; Networks and Matroids. Holt Rinehart and Wilson New York 1976.]]  E. Lawler. Combinatorial optimization; Networks and Matroids. Holt Rinehart and Wilson New York 1976.]]"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02993903"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/314464.314625"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1750"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1919"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202354"},{"key":"e_1_3_2_1_63_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-60692-0_39","volume-title":"Proc. 15th Internat. Conf. on Foundations of Software Technology and Theoretical Computer Science","author":"Roychoudhury A.","year":"1995","unstructured":"A. Roychoudhury and S. Sur-Kolay . Efficient algorithm for vertex arboricity of planar graphs . In Proc. 15th Internat. Conf. on Foundations of Software Technology and Theoretical Computer Science , Lecture Notes in Computer Science , Springer , Berlin , volume 1026 , pages 37 -- 51 , 1995 .]] A. Roychoudhury and S. Sur-Kolay. Efficient algorithm for vertex arboricity of planar graphs. In Proc. 15th Internat. Conf. on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, Springer, Berlin, volume 1026, pages 37--51, 1995.]]"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2101"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(77)90031-4"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.02.013"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100061521"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2013"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1062"},{"key":"e_1_3_2_1_70_1","volume-title":"Congr. Numer., 115: 249--283","author":"Toft B.","year":"1996","unstructured":"B. Toft . A survey of Hadwiger's conjecture. Congr. Numer., 115: 249--283 , 1996 .]] B. Toft. A survey of Hadwiger's conjecture. Congr. Numer., 115:249--283, 1996.]]"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1049"},{"key":"e_1_3_2_1_72_1","first-page":"3","article-title":"Coloring the vertices of a graph in prescribed colors. Metody Diskret. Anal. v Teorii Kodov i Schem (","volume":"29","author":"Vizing V. G.","year":"1976","unstructured":"V. G. Vizing . Coloring the vertices of a graph in prescribed colors. Metody Diskret. Anal. v Teorii Kodov i Schem ( In Russian) , 29 : 3 -- 10 , 1976 .]] V. G. Vizing. Coloring the vertices of a graph in prescribed colors. Metody Diskret. Anal. v Teorii Kodov i Schem (In Russian), 29:3--10, 1976.]]","journal-title":"Russian)"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90579-I"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01594196"},{"key":"e_1_3_2_1_75_1","first-page":"45","volume-title":"Pitman Research Notes","volume":"218","author":"Woodall D. R.","year":"1990","unstructured":"D. R. Woodall . Improper colourings of graphs. In Graph Colourings (ed. R. Nelson and R. J. Wilson) , Pitman Research Notes , Longman , volume 218 , pages 45 -- 63 , 1990 .]] D. R. Woodall. Improper colourings of graphs. In Graph Colourings (ed. R. Nelson and R. J. Wilson), Pitman Research Notes, Longman, volume 218, pages 45--63, 1990.]]"}],"event":{"name":"STOC06: Symposium on Theory of Computing","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Seattle WA USA","acronym":"STOC06"},"container-title":["Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132576","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132516.1132576","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:51Z","timestamp":1750263531000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132576"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5,21]]},"references-count":75,"alternative-id":["10.1145\/1132516.1132576","10.1145\/1132516"],"URL":"https:\/\/doi.org\/10.1145\/1132516.1132576","relation":{},"subject":[],"published":{"date-parts":[[2006,5,21]]},"assertion":[{"value":"2006-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}