{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T03:18:59Z","timestamp":1774063139577,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,3,5]],"date-time":"2018-03-05T00:00:00Z","timestamp":1520208000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00493-017-3068-3","type":"journal-article","created":{"date-parts":[[2018,3,5]],"date-time":"2018-03-05T02:26:02Z","timestamp":1520216762000},"page":"887-934","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["A Brooks-Type Result for Sparse Critical Graphs"],"prefix":"10.1007","volume":"38","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","published-online":{"date-parts":[[2018,3,5]]},"reference":[{"key":"3068_CR1","volume-title":"Private communication","author":"V. Aksenov","year":"1976","unstructured":"V. Aksenov: Private communication (1976)."},{"key":"3068_CR2","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1016\/j.disc.2012.11.011","volume":"313","author":"O. V. Borodin","year":"2013","unstructured":"O. V. Borodin: Colorings of plane graphs: A survey, Discrete Math. 313 (2013), 517\u2013533.","journal-title":"Discrete Math."},{"key":"3068_CR3","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.ejc.2014.03.009","volume":"41","author":"O. V. Borodin","year":"2014","unstructured":"O. V. Borodin, Z. Dvor\u00e1k, A. V. Kostochka, B. Lidick\u00fd and M. Yancey: Planar 4-critical graphs with four triangles, European J. of Combinatorics 41 (2014), 138\u2013151.","journal-title":"European J. of Combinatorics"},{"key":"3068_CR4","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.jctb.2013.10.002","volume":"104","author":"O. V. Borodin","year":"2014","unstructured":"O. V. Borodin and A. V. Kostochka: Defective 2-colorings of sparse graphs, J. Combin. Theory (B) 104 (2014), 72\u201380.","journal-title":"J. Combin. Theory (B)"},{"key":"3068_CR5","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/j.ejc.2013.05.002","volume":"36","author":"O. V. Borodin","year":"2014","unstructured":"O. V. Borodin, A. V. Kostochka, B. Lidick\u00fd and M. Yancey: Short proofs of coloring theorems on planar graphs, European J. of Combinatorics 36 (2014), 314\u2013321.","journal-title":"European J. of Combinatorics"},{"issue":"22","key":"3068_CR6","doi-asserted-by":"publisher","first-page":"2638","DOI":"10.1016\/j.disc.2013.07.014","volume":"313","author":"O. V. Borodin","year":"2013","unstructured":"O. V. Borodin, A. V. Kostochka and M. Yancey: On 1-improper 2-coloring of sparse graphs, Discrete Mathematics 313 (2013), no. 22, 2638\u20132649.","journal-title":"Discrete Mathematics"},{"key":"3068_CR7","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/BF01238034","volume":"54","author":"G. A. Dirac","year":"1951","unstructured":"G. A. Dirac: Note on the colouring of graphs, Math. Z. 54 (1951), 347\u2013353.","journal-title":"Math. Z."},{"key":"3068_CR8","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 (1952), 85\u201392.","journal-title":"J. London Math. Soc."},{"key":"3068_CR9","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1112\/plms\/s3-2.1.69","volume":"2","author":"G. A. Dirac","year":"1952","unstructured":"G. A. Dirac: Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952), 69\u201381.","journal-title":"Proc. London Math. Soc."},{"key":"3068_CR10","doi-asserted-by":"publisher","first-page":"42","DOI":"10.4064\/fm-40-1-42-55","volume":"40","author":"G. A. Dirac","year":"1953","unstructured":"G. A. Dirac: The structure of k-chromatic graphs, Fund. Math. 40 (1953), 42\u201355.","journal-title":"Fund. Math."},{"key":"3068_CR11","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1112\/jlms\/s1-31.4.460","volume":"31","author":"G. A. Dirac","year":"1956","unstructured":"G. A. Dirac: Map colour theorems related to the Heawood colour formula, J. London Math. Soc. 31 (1956), 460\u2013471.","journal-title":"J. London Math. Soc."},{"key":"3068_CR12","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1112\/plms\/s3-7.1.161","volume":"7","author":"G. A. Dirac","year":"1957","unstructured":"G. A. Dirac: A theorem of R. L. Brooks and a conjecture of H. Hadwiger, Proc. London Math. Soc. 7 (1957), 161\u2013195.","journal-title":"Proc. London Math. Soc."},{"key":"3068_CR13","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1515\/crll.1964.214-215.43","volume":"214\u2013215","author":"G. A. Dirac","year":"1964","unstructured":"G. A. Dirac: On the structure of 5- and 6-chromatic abstract graphs, J. Reine Angew. Math. 214\u2013215 (1964), 43\u201352.","journal-title":"J. Reine Angew. Math."},{"key":"3068_CR14","first-page":"150","volume":"268\/269","author":"G. A. Dirac","year":"1974","unstructured":"G. A. Dirac: The number of edges in critical graphs, J. Reine Angew. Math. 268\/269 (1974), 150\u2013164.","journal-title":"J. Reine Angew. Math."},{"key":"3068_CR15","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1007\/s00493-009-2267-y","volume":"29","author":"B. Farzad","year":"2009","unstructured":"B. Farzad and M. Molloy: On the edge-density of 4-critical graphs, Combinatorica 29 (2009), 665\u2013689.","journal-title":"Combinatorica"},{"key":"3068_CR16","first-page":"165","volume":"8","author":"T. Gallai","year":"1963","unstructured":"T. Gallai: Kritische Graphen I, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963), 165\u2013192.","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"3068_CR17","first-page":"373","volume":"8","author":"T. Gallai","year":"1963","unstructured":"T. Gallai: Kritische Graphen II, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963), 373\u2013395.","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"3068_CR18","first-page":"109","volume":"8","author":"H. Gr\u00f6tzsch","year":"1959","unstructured":"H. Gr\u00f6tzsch: 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 8 (1958\/1959), 109\u2013120 (in German).","journal-title":"Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe"},{"key":"3068_CR19","first-page":"116","volume":"10","author":"G. Haj\u00f3s","year":"1961","unstructured":"G. Haj\u00f3s: \u00dcber eine Konstruktion nicht-n-f\u00e4rbbarer Graphen, Wiss. Z. Martin-Luther-Unive. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 116\u2013117.","journal-title":"Wiss. Z. Martin-Luther-Unive. Halle-Wittenberg Math.-Natur. Reihe"},{"key":"3068_CR20","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/0110037","volume":"10","author":"S. L. Hakimi","year":"1962","unstructured":"S. L. Hakimi: On realizability of a set of integers as degrees of the vertices of a linear graph. I., J. Soc. Indust. Appl. Math. 10 (1962), 496\u2013506.","journal-title":"J. Soc. Indust. Appl. Math."},{"key":"3068_CR21","volume-title":"Graph Coloring Problems","author":"T. R. Jensen","year":"1995","unstructured":"T. R. Jensen and B. Toft: Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1995."},{"key":"3068_CR22","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0012-365X(00)00206-5","volume":"229","author":"T. R. Jensen","year":"2001","unstructured":"T. R. Jensen and B. Toft: 25 pretty graph colouring problems, Discrete Math. 229 (2001), 167\u2013169.","journal-title":"Discrete Math."},{"key":"3068_CR23","unstructured":"H. Kierstead and L. Rabern: Personal communication."},{"key":"3068_CR24","first-page":"87","volume-title":"Graph Theory and Combinatorial Biology, Balatonlelle","author":"A. V. Kostochka","year":"1999","unstructured":"A. V. Kostochka and M. Stiebitz: Excess in colour-critical graphs, in: Graph Theory and Combinatorial Biology, Balatonlelle (Hungary), 1996, Bolyai Society, Mathematical Studies 7, Budapest, 1999, 87\u201399."},{"key":"3068_CR25","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/S0095-8956(02)00035-7","volume":"87","author":"A. V. Kostochka","year":"2003","unstructured":"A. V. Kostochka and M. Stiebitz: A new lower bound on the number of edges in colour-critical graphs and hypergraphs, J. Comb. Theory, Series B. 87 (2003), 374\u2013402.","journal-title":"J. Comb. Theory, Series B."},{"key":"3068_CR26","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.jctb.2014.05.002","volume":"109","author":"A. V. Kostochka","year":"2014","unstructured":"A. V. Kostochka and M. Yancey: Ore's Conjecture on color-critical graphs is almost true, J. Comb. Theory, Series B. 109 (2014), 73\u2013101.","journal-title":"J. Comb. Theory, Series B."},{"key":"3068_CR27","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s00493-014-3020-x","volume":"34","author":"A. V. Kostochka","year":"2014","unstructured":"A. V. Kostochka and M. Yancey: Ore's Conjecture for k=4 and Gr\u00f6tzsch Theorem, Combinatorica 34 (2014), 323\u2013329.","journal-title":"Combinatorica"},{"key":"3068_CR28","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/BF01215921","volume":"17","author":"M. Krivelevich","year":"1997","unstructured":"M. Krivelevich: On the minimal number of edges in color-critical graphs, Combinatorica 17 (1997), 401\u2013426.","journal-title":"Combinatorica"},{"key":"3068_CR29","volume-title":"The Four Color Problem","author":"O. Ore","year":"1967","unstructured":"O. Ore: The Four Color Problem, Academic Press, New York, 1967."},{"key":"3068_CR30","unstructured":"L. Postle: Personal communication."},{"key":"3068_CR31","first-page":"211","volume":"55","author":"R. Steinberg","year":"1993","unstructured":"R. Steinberg: The state of the three color problem, Quo Vadis, Graph Theory?, Ann. Discrete Math. 55 (1993), 211\u2013248.","journal-title":"Quo Vadis, Graph Theory?, Ann. Discrete Math."},{"key":"3068_CR32","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0095-8956(74)90057-4","volume":"16","author":"B. Toft","year":"1974","unstructured":"B. Toft: Color-critical graphs and hypergraphs, J. Combin. Theory 16 (1974), 145\u2013161.","journal-title":"J. Combin. Theory"},{"key":"3068_CR33","unstructured":"B. Toft: Personal communication."},{"key":"3068_CR34","volume-title":"Handbook of graph theory","author":"Z. Tuza","year":"2004","unstructured":"Zs Tuza: Graph coloring, in: Handbook of graph theory (J. L. Gross and J. Yellen Eds.), CRC Press, Boca Raton, FL, 2004. xiv+1167."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-017-3068-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-017-3068-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-017-3068-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T05:38:28Z","timestamp":1660541908000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-017-3068-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,5]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["3068"],"URL":"https:\/\/doi.org\/10.1007\/s00493-017-3068-3","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,5]]},"assertion":[{"value":"13 December 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2017","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 March 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}