{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T16:59:28Z","timestamp":1725728368792},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385353"},{"type":"electronic","value":"9783642385360"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38536-0_20","type":"book-chapter","created":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T01:03:04Z","timestamp":1370221384000},"page":"224-234","source":"Crossref","is-referenced-by-count":1,"title":["On Coloring of Sparse Graphs"],"prefix":"10.1007","author":[{"given":"Alexandr","family":"Kostochka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Yancey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"#cr-split#-20_CR1.1","unstructured":"Borodin, O.V., Ivanova, A.O.: Near-proper vertex 2-colorings of sparse graphs. Diskretn. Anal. Issled. Oper.\u00a016(2), 16-20 (2009) (in Russian)"},{"key":"#cr-split#-20_CR1.2","doi-asserted-by":"crossref","unstructured":"Translated in: Journal of Applied and Industrial Mathematics 4(1), 21-23 (2010)","DOI":"10.1134\/S1990478910010047"},{"issue":"2","key":"20_CR2","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/jgt.20516","volume":"67","author":"O.V. Borodin","year":"2011","unstructured":"Borodin, O.V., Ivanova, A.O.: List strong linear 2-arboricity of sparse graphs. J. Graph Theory\u00a067(2), 83\u201390 (2011)","journal-title":"J. Graph Theory"},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/jgt.20467","volume":"65","author":"O.V. Borodin","year":"2010","unstructured":"Borodin, O.V., Ivanova, A.O., Montassier, M., Ochem, P., Raspaud, A.: Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. J. Graph Theory\u00a065, 83\u201393 (2010)","journal-title":"J. Graph Theory"},{"issue":"17","key":"20_CR4","doi-asserted-by":"publisher","first-page":"1947","DOI":"10.1016\/j.dam.2011.06.021","volume":"159","author":"O.V. Borodin","year":"2011","unstructured":"Borodin, O.V., Ivanova, A.O., Montassier, M., Raspaud, A. (k,j)-Coloring of sparse graphs. Discrete Applied Mathematics\u00a0159(17), 1947\u20131953 (2011)","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"20_CR5","doi-asserted-by":"crossref","first-page":"1128","DOI":"10.1016\/j.disc.2011.11.031","volume":"312","author":"O.V. Borodin","year":"2012","unstructured":"Borodin, O.V., Ivanova, A.O., Montassier, M., Raspaud, A.: (k,1)-Coloring of sparse graphs. Discrete Math\u00a0312(6), 1128\u20131135 (2012)","journal-title":"Discrete Math"},{"issue":"5","key":"20_CR6","first-page":"1004","volume":"52","author":"O.V. Borodin","year":"2011","unstructured":"Borodin, O.V., Kostochka, A.V.: Vertex partitions of sparse graphs into an independent vertex set and subgraph of maximum degree at most one (Russian). Sibirsk. Mat. Zh.\u00a052(5), 1004\u20131010 (2011); Translation in: Siberian Mathematical Journal 52(5), 796\u2013801","journal-title":"Sibirsk. Mat. Zh."},{"key":"20_CR7","unstructured":"Borodin, O.V., Kostochka, A.V.: Defective 2-colorings of sparse graphs (submitted)"},{"key":"20_CR8","unstructured":"Borodin, O.V., Kostochka, A.V., Lidick\u00fd, B., Yancey, M.: Short proofs of coloring theorems on planar graphs (submitted)"},{"key":"20_CR9","unstructured":"Borodin, O.V., Kostochka, A.V., Yancey, M.: On 1-improper 2-coloring of sparse graphs (submitted)"},{"key":"20_CR10","first-page":"219","volume":"43","author":"R. Corr\u011ba","year":"2009","unstructured":"Corr\u011ba, R., Havet, F., Sereni, J.-S.: About a Brooks-type theorem for improper colouring. Australas. J. Combin.\u00a043, 219\u2013230 (2009)","journal-title":"Australas. J. Combin."},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R.L. Brooks","year":"1941","unstructured":"Brooks, R.L.: On colouring the nodes of a network. Math. Proc. Cambridge Philos. Soc.\u00a037, 194\u2013197 (1941)","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"20_CR12","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/BF01238034","volume":"54","author":"G.A. Dirac","year":"1951","unstructured":"Dirac, G.A.: Note on the colouring of graphs. Math. Z.\u00a054, 347\u2013353 (1951)","journal-title":"Math. Z."},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/jlms\/s1-27.1.85","volume":"27","author":"G.A. Dirac","year":"1952","unstructured":"Dirac, G.A.: A property of 4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc.\u00a027, 85\u201392 (1952)","journal-title":"J. London Math. Soc."},{"issue":"2","key":"20_CR14","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1112\/plms\/s3-2.1.69","volume":"3","author":"G.A. Dirac","year":"1952","unstructured":"Dirac, G.A.: Some theorems on abstract graphs. Proc. London Math.\u00a03(2), 69\u201381 (1952)","journal-title":"Proc. London Math."},{"key":"20_CR15","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1112\/jlms\/s1-31.4.460","volume":"31","author":"G.A. Dirac","year":"1956","unstructured":"Dirac, G.A.: Map colour theorems related to the Heawood colour formula. J. London Math. Soc.\u00a031, 460\u2013471 (1956)","journal-title":"J. London Math. Soc."},{"issue":"3","key":"20_CR16","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1112\/plms\/s3-7.1.161","volume":"7","author":"G.A. Dirac","year":"1957","unstructured":"Dirac, G.A.: A theorem of R.\u00a0L.\u00a0Brooks and a conjecture of H.\u00a0Hadwiger. Proc. London Math. Soc.\u00a07(3), 161\u2013195 (1957)","journal-title":"Proc. London Math. Soc."},{"issue":"269","key":"20_CR17","first-page":"150","volume":"268","author":"G.A. Dirac","year":"1974","unstructured":"Dirac, G.A.: The number of edges in critical graphs. J. Reine Angew. Math.\u00a0268(269), 150\u2013164 (1974)","journal-title":"J. Reine Angew. Math."},{"key":"20_CR18","unstructured":"Dorbec, P., Kaiser, T., Montassier, M., Raspaud, A.: Limits of near-coloring of sparse graphs. To Appear in J. Graph Theory"},{"key":"20_CR19","unstructured":"Esperet, L., Montassier, M., Ochem, P., Pinlou, A.: A Complexity Dichotomy for the Coloring of Sparse Graphs. To Appear in J. Graph Theory"},{"key":"20_CR20","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1007\/s00493-009-2267-y","volume":"29","author":"B. Farzad","year":"2009","unstructured":"Farzad, B., Molloy, M.: On the edge-density of 4-critical graphs. Combinatorica\u00a029, 665\u2013689 (2009)","journal-title":"Combinatorica"},{"key":"20_CR21","first-page":"165","volume":"8","author":"T. Gallai","year":"1963","unstructured":"Gallai, T.: Kritische Graphen I. Publ. Math. Inst. Hungar. Acad. Sci.\u00a08, 165\u2013192 (1963)","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"20_CR22","first-page":"373","volume":"8","author":"T. Gallai","year":"1963","unstructured":"Gallai, T.: Kritische Graphen II. Publ. Math. Inst. Hungar. Acad. Sci.\u00a08, 373\u2013395 (1963)","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"20_CR23","first-page":"450","volume":"4","author":"A.N. Glebov","year":"2007","unstructured":"Glebov, A.N., Zambalaeva, D.Z.: Path partitions of planar graphs. Sib. Elektron. Mat. Izv.\u00a04, 450\u2013459 (2007) (Russian)","journal-title":"Sib. Elektron. Mat. Izv."},{"key":"20_CR24","unstructured":"Gr\u00f6tzsch, H.: Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz f\u00fcr dreikreisfreie Netze auf der Kugel. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe\u00a08, 109\u2013120 (1958\/1959) (in Russian)"},{"key":"20_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/11604686_8","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F. Havet","year":"2005","unstructured":"Havet, F., Sereni, J.-S.: Channel assignment and improper choosability of graphs. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 81\u201390. Springer, Heidelberg (2005)"},{"key":"20_CR26","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1002\/1097-0118(200007)34:3<234::AID-JGT4>3.0.CO;2-G","volume":"34","author":"T. Jensen","year":"2000","unstructured":"Jensen, T., Thomassen, C.: The color space of a graph. J. Graph Theory\u00a034, 234\u2013245 (2000)","journal-title":"J. Graph Theory"},{"key":"20_CR27","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","volume-title":"Graph Coloring Problems","author":"T.R. Jensen","year":"1995","unstructured":"Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, New York (1995)"},{"key":"20_CR28","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0012-365X(00)00206-5","volume":"229","author":"T.R. Jensen","year":"2001","unstructured":"Jensen, T.R., Toft, B.: 25 pretty graph colouring problems. Discrete Math\u00a0229, 167\u2013169 (2001)","journal-title":"Discrete Math"},{"key":"20_CR29","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"#cr-split#-20_CR30.1","unstructured":"Kostochka, A.V., Stiebitz, M.: Excess in colour-critical graphs. In: Graph Theory and Combinatorial Biology, Balatonlelle, Hungary (1996)"},{"key":"#cr-split#-20_CR30.2","unstructured":"Bolyai Society, Mathematical Studies, Budapest, vol. 7, pp. 87-99 (1999)"},{"key":"20_CR31","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/S0095-8956(02)00035-7","volume":"87","author":"A.V. Kostochka","year":"2003","unstructured":"Kostochka, A.V., Stiebitz, M.: A new lower bound on the number of edges in colour-critical graphs and hypergraphs. Journal of Combinatorial Theory, Series B\u00a087, 374\u2013402 (2003)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"20_CR32","unstructured":"Kostochka, A.V., Yancey, M.: Ore\u2019s Conjecture on color-critical graphs is almost true (submitted)"},{"key":"20_CR33","unstructured":"Kostochka, A.V., Yancey, M.: Ore\u2019s Conjecture for k = 4 and Gr\u00f6tzsch Theorem. Combinatorica (accepted)"},{"key":"20_CR34","unstructured":"Kostochka, A.V., Yancey, M.: A Brooks-type result for sparse critical graphs (submitted)"},{"key":"20_CR35","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/BF01215921","volume":"17","author":"M. Krivelevich","year":"1997","unstructured":"Krivelevich, M.: On the minimal number of edges in color-critical graphs. Combinatorica\u00a017, 401\u2013426 (1997)","journal-title":"Combinatorica"},{"key":"20_CR36","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1002\/jgt.3190180108","volume":"18","author":"A. Kurek","year":"1994","unstructured":"Kurek, A., Rucin\u2019ski, A.: Globally sparse vertex-Ramsey graphs. J. Graph Theory\u00a018, 73\u201381 (1994)","journal-title":"J. Graph Theory"},{"key":"20_CR37","volume-title":"The Four Color Problem","author":"O. Ore","year":"1967","unstructured":"Ore, O.: The Four Color Problem. Academic Press, New York (1967)"},{"key":"20_CR38","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.jctb.2004.05.001","volume":"92","author":"R. Thomas","year":"2004","unstructured":"Thomas, R., Walls, B.: Three-coloring Klein bottle graphs of girth five. J. Combin. Theory Ser. B\u00a092, 115\u2013135 (2004)","journal-title":"J. Combin. Theory Ser. B"},{"key":"20_CR39","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0095-8956(03)00029-7","volume":"88","author":"C. Thomassen","year":"2003","unstructured":"Thomassen, C.: A short list color proof of Gr\u00f6tzsch\u2019s theorem. J. Combin. Theory Ser. B\u00a088, 189\u2013192 (2003)","journal-title":"J. Combin. Theory Ser. B"},{"key":"20_CR40","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0095-8956(74)90057-4","volume":"16","author":"B. Toft","year":"1974","unstructured":"Toft, B.: Color-critical graphs and hypergraphs. J. Combin. Theory\u00a016, 145\u2013161 (1974)","journal-title":"J. Combin. Theory"},{"key":"20_CR41","unstructured":"Toft, B.: 75 graph-colouring problems. In: Keynes, M. (ed.) Graph Colourings, pp. 9\u201335 (1988) Pitman Res. Notes Math. Ser., vol. 218. Longman Sci. Tech., Harlow (1990)"},{"key":"20_CR42","unstructured":"Tuza, Z.: Graph coloring. In: Gross, J.L., Yellen, J. (eds.) Handbook of Graph Theory, xiv+1167 pp. CRC Press, Boca Raton (2004)"},{"key":"20_CR43","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D. Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. Theory of Computing\u00a03, 103\u2013128 (2007)","journal-title":"Theory of Computing"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38536-0_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T18:47:23Z","timestamp":1645642043000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}