{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:55Z","timestamp":1759638055024},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,7,3]],"date-time":"2010-07-03T00:00:00Z","timestamp":1278115200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,7]]},"DOI":"10.1007\/s00453-010-9425-x","type":"journal-article","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T19:43:41Z","timestamp":1278099821000},"page":"553-568","source":"Crossref","is-referenced-by-count":29,"title":["Injective Colorings of Graphs with Low Average Degree"],"prefix":"10.1007","volume":"60","author":[{"given":"Daniel W.","family":"Cranston","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seog-Jin","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gexin","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,7,3]]},"reference":[{"key":"9425_CR1","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1515\/crll.1989.394.180","volume":"394","author":"O.V. Borodin","year":"1989","unstructured":"Borodin, O.V.: On the total coloring of planar graphs. J.\u00a0Reine Angew. Math. 394, 180\u2013185 (1989)","journal-title":"J.\u00a0Reine Angew. Math."},{"key":"9425_CR2","first-page":"22","volume":"48","author":"O.V. Borodin","year":"1990","unstructured":"Borodin, O.V.: An extension of Kotzig\u2019s theorem and the list edge colouring of planar graphs. Mat. Zametki 48, 22\u201328 (1990) (in Russian)","journal-title":"Mat. Zametki"},{"key":"9425_CR3","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1006\/jctb.1997.1780","volume":"71","author":"O.V. Borodin","year":"1997","unstructured":"Borodin, O.V., Kostochka, A.V., Woodall, D.R.: List edge and list total colourings of multigraphs. J.\u00a0Comb. Theory B 71, 184\u2013204 (1997)","journal-title":"J.\u00a0Comb. Theory B"},{"issue":"1","key":"9425_CR4","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M. Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164(1), 51\u2013229 (2006). http:\/\/annals.princeton.edu\/annals\/2006\/164-1\/p02.xhtml","journal-title":"Ann. Math."},{"key":"9425_CR5","first-page":"2","volume":"70","author":"G. Cornu\u00e9jols","year":"2003","unstructured":"Cornu\u00e9jols, G.: The strong perfect graph theorem. Optima 70, 2\u20136 (2003). http:\/\/integer.tepper.cmu.edu\/webpub\/optima.pdf","journal-title":"Optima"},{"key":"9425_CR6","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1002\/jgt.20273","volume":"57","author":"D.W. Cranston","year":"2008","unstructured":"Cranston, D.W., Kim, S.-J.: List-coloring the square of a subcubic graph. J.\u00a0Graph Theory 57, 65\u201387 (2008)","journal-title":"J.\u00a0Graph Theory"},{"key":"9425_CR7","unstructured":"Cranston, D.W., Kim, S.-J., Yu, G.: Injective colorings of sparse graphs. Discrete Math. (to appear)"},{"issue":"3","key":"9425_CR8","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1016\/j.disc.2009.04.020","volume":"310","author":"A. Doyon","year":"2010","unstructured":"Doyon, A., Hahn, G., Raspaud, A.: On the injective chromatic number of sparse graphs. Discrete Math. 310(3), 585\u2013590 (2010)","journal-title":"Discrete Math."},{"key":"9425_CR9","first-page":"125","volume":"26","author":"P. Erd\u0151s","year":"1979","unstructured":"Erd\u0151s, P., Rubin, A., Taylor, H.: Choosability in graphs. Congr. Numer. 26, 125\u2013157 (1979)","journal-title":"Congr. Numer."},{"key":"9425_CR10","doi-asserted-by":"crossref","first-page":"1547","DOI":"10.1109\/TIT.2007.892768","volume":"53","author":"J. Fridrich","year":"2007","unstructured":"Fridrich, J., Lisonek, P.: Grid colorings in steganography. IEEE Trans. Inf. Theory 53, 1547\u20131549 (2007)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9425_CR11","volume-title":"Computers and Intractability: A\u00a0Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A\u00a0Guide to the Theory of NP-completeness. Freeman, New York (1979)"},{"key":"9425_CR12","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0012-365X(01)00466-6","volume":"256","author":"G. Hahn","year":"2002","unstructured":"Hahn, G., Kratochv\u00edl, J., \u0160ir\u00e1\u0148, J., Sotteau, D.: On the injective chromatic number of graphs. Discrete Math. 256, 179\u2013192 (2002)","journal-title":"Discrete Math."},{"key":"9425_CR13","unstructured":"Hahn, G., Raspaud, A., Wang, W.: On the injective coloring of K 4-minor free graphs. Preprint (2006). http:\/\/www.labri.fr\/perso\/lepine\/Rapports_internes\/RR-140106.ps.gz"},{"key":"9425_CR14","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1002\/jgt.10077","volume":"42","author":"J. Heuvel van\u00a0den","year":"2002","unstructured":"van\u00a0den Heuvel, J., McGuinness, S.: Coloring the square of a planar graph. J.\u00a0Graph Theory 42, 110\u2013124 (2002)","journal-title":"J.\u00a0Graph Theory"},{"issue":"18","key":"9425_CR15","doi-asserted-by":"crossref","first-page":"5636","DOI":"10.1016\/j.disc.2008.04.005","volume":"309","author":"B. Lu\u017ear","year":"2009","unstructured":"Lu\u017ear, B., \u0160krekovski, R., Tancer, M.: Injective colorings of planar graphs with few colors. Discrete Math. 309(18), 5636\u20135649 (2009)","journal-title":"Discrete Math."},{"key":"9425_CR16","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.jctb.2004.12.005","volume":"94","author":"M. Molloy","year":"2005","unstructured":"Molloy, M., Salavatipour, M.R.: A\u00a0bound on the chromatic number of the square of a planar graph. J.\u00a0Comb. Theory B 94, 189\u2013213 (2005)","journal-title":"J.\u00a0Comb. Theory B"},{"key":"9425_CR17","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1006\/jctb.1997.1750","volume":"70","author":"N. Robertson","year":"1997","unstructured":"Robertson, N., Sanders, D.P., Seymour, P.D., Thomas, R.: The four colour theorem. J.\u00a0Comb. Theory B 70, 2\u201344 (1997)","journal-title":"J.\u00a0Comb. Theory B"},{"key":"9425_CR18","unstructured":"Robertson, N., Sanders, D.P., Seymour, P.D., Thomas, R.: The four color theorem. http:\/\/people.math.gatech.edu\/~thomas\/FC\/fourcolor.html"},{"key":"9425_CR19","unstructured":"Seymour, P.: How the proof of the strong perfect graph conjecture was found. http:\/\/users.encs.concordia.ca\/~chvatal\/perfect\/pds.pdf"},{"key":"9425_CR20","first-page":"3","volume":"29","author":"V.G. Vizing","year":"1976","unstructured":"Vizing, V.G.: Coloring the vertices of a graph in prescribed colors. Diskretn. Anal. 29, 3\u201310 (1976) (in Russian)","journal-title":"Diskretn. Anal."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9425-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9425-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9425-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:06Z","timestamp":1559137506000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9425-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,3]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["9425"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9425-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,3]]}}}