{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T07:06:55Z","timestamp":1790752015827,"version":"4.1.0"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319687049","type":"print"},{"value":"9783319687056","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-68705-6_9","type":"book-chapter","created":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T02:06:22Z","timestamp":1509501982000},"page":"113-126","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Defective Coloring on Classes of Perfect Graphs"],"prefix":"10.1007","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Lampis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valia","family":"Mitsou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,11,2]]},"reference":[{"issue":"13","key":"9_CR1","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1016\/j.disc.2010.08.013","volume":"311","author":"N Achuthan","year":"2011","unstructured":"Achuthan, N., Achuthan, N.R., Simanihuruk, M.: On minimal triangle-free graphs with prescribed k-defective chromatic number. Discret. Math. 311(13), 1119\u20131127 (2011)","journal-title":"Discret. Math."},{"key":"9_CR2","first-page":"33","volume":"47","author":"JA Andrews","year":"1985","unstructured":"Andrews, J.A., Jacobson, M.S.: On a generalization of chromatic number. Congr. Numer. 47, 33\u201348 (1985)","journal-title":"Congr. Numer."},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.jda.2012.07.001","volume":"16","author":"J Ara\u00fajo","year":"2012","unstructured":"Ara\u00fajo, J., Bermond, J.-C., Giroire, F., Havet, F., Mazauric, D., Modrzejewski, R.: Weighted improper colouring. J. Discret. Algorithms 16, 53\u201366 (2012)","journal-title":"J. Discret. Algorithms"},{"issue":"4","key":"9_CR4","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1002\/jgt.3190110408","volume":"11","author":"D Archdeacon","year":"1987","unstructured":"Archdeacon, D.: A note on defective colorings of graphs in surfaces. J. Graph Theory 11(4), 517\u2013519 (1987)","journal-title":"J. Graph Theory"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.dam.2013.11.018","volume":"182","author":"C Archetti","year":"2015","unstructured":"Archetti, C., Bianchessi, N., Hertz, A., Colombet, A., Gagnon, F.: Directed weighted improper coloring forcellular channel allocation. Discret. Appl. Math. 182, 46\u201360 (2015)","journal-title":"Discret. Appl. Math."},{"issue":"10","key":"9_CR6","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1016\/j.ipl.2015.05.007","volume":"115","author":"J Bang-Jensen","year":"2015","unstructured":"Bang-Jensen, J., Halld\u00f3rsson, M.M.: Vertex coloring edge-weighted digraphs. Inf. Process. Lett. 115(10), 791\u2013796 (2015)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9_CR7","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1142\/S1793830910000747","volume":"2","author":"J-C Bermond","year":"2010","unstructured":"Bermond, J.-C., Havet, F., Huc, F., Sales, C.L.: Improper coloring of weighted grid and hexagonal graphs. Discret. Math. Algorithms Appl. 2(3), 395\u2013412 (2010)","journal-title":"Discret. Math. Algorithms Appl."},{"issue":"1\u20132","key":"9_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9_CR9","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3), 255\u2013269 (2008)","journal-title":"Comput. J."},{"issue":"22","key":"9_CR10","doi-asserted-by":"publisher","first-page":"2638","DOI":"10.1016\/j.disc.2013.07.014","volume":"313","author":"OV Borodin","year":"2013","unstructured":"Borodin, O.V., Kostochka, A.V., Yancey, M.: On 1-improper 2-coloring of sparse graphs. Discret. Math. 313(22), 2638\u20132649 (2013)","journal-title":"Discret. Math."},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. SIAM (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"9_CR12","unstructured":"Choi, I., Esperet, L.: Improper coloring of graphs on surfaces. arXiv e-prints, March 2016"},{"issue":"2","key":"9_CR13","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1002\/jgt.3190100207","volume":"10","author":"LJ Cowen","year":"1986","unstructured":"Cowen, L.J., Cowen, R.H., Woodall, D.R.: Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. J. Graph Theory 10(2), 187\u2013195 (1986)","journal-title":"J. Graph Theory"},{"issue":"3","key":"9_CR14","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T","volume":"24","author":"L Cowen","year":"1997","unstructured":"Cowen, L., Goddard, W., Jesurum, C.E.: Defective coloring revisited. J. Graph Theory 24(3), 205\u2013219 (1997)","journal-title":"J. Graph Theory"},{"key":"9_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015)"},{"key":"9_CR16","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)","edition":"4"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0167-5060(08)70374-1","volume":"55","author":"M Frick","year":"1993","unstructured":"Frick, M.: A survey of (m, k)-colorings. Ann. Discret. Math. 55, 45\u201357 (1993)","journal-title":"Ann. Discret. Math."},{"issue":"1\u20133","key":"9_CR18","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0012-365X(94)90260-7","volume":"126","author":"M Frick","year":"1994","unstructured":"Frick, M., Henning, M.A.: Extremal results on defective colorings of graphs. Discret. Math. 126(1\u20133), 151\u2013158 (1994)","journal-title":"Discret. Math."},{"key":"9_CR19","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"2","key":"9_CR20","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1002\/jgt.21868","volume":"81","author":"W Goddard","year":"2016","unstructured":"Goddard, W., Honghai, X.: Fractional, circular, and defective coloring of series-parallel graphs. J. Graph Theory 81(2), 146\u2013153 (2016)","journal-title":"J. Graph Theory"},{"issue":"1","key":"9_CR21","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0012-365X(78)90178-4","volume":"24","author":"MC Golumbic","year":"1978","unstructured":"Golumbic, M.C.: Trivially perfect graphs. Discret. Math. 24(1), 105\u2013107 (1978)","journal-title":"Discret. Math."},{"key":"9_CR22","doi-asserted-by":"publisher","first-page":"362 S","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, vol. 4060 XII, p. 362 S. Springer, Berlin (1988)"},{"key":"9_CR23","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.entcs.2016.03.013","volume":"322","author":"BA Gudmundsson","year":"2016","unstructured":"Gudmundsson, B.A., Magn\u00fasson, T.K., S\u00e6mundsson, B.O.: Bounds and fixed-parameter algorithms for weighted improper coloring. Electron. Notes Theor. Comput. Sci. 322, 181\u2013195 (2016)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"issue":"3","key":"9_CR24","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1002\/net.20318","volume":"54","author":"F Havet","year":"2009","unstructured":"Havet, F., Kang, R.J., Sereni, J.-S.: Improper coloring of unit disk graphs. Networks 54(3), 150\u2013164 (2009)","journal-title":"Networks"},{"issue":"3","key":"9_CR25","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1002\/jgt.20155","volume":"52","author":"F Havet","year":"2006","unstructured":"Havet, F., Sereni, J.-S.: Improper choosability of graphs and maximum average degree. J. Graph Theory 52(3), 181\u2013199 (2006)","journal-title":"J. Graph Theory"},{"issue":"4","key":"9_CR26","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR27","unstructured":"Kang, R.J.: Improper colourings of graphs. Ph.D. thesis, University of Oxford, UK (2008)"},{"issue":"1","key":"9_CR28","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1017\/S0963548309990216","volume":"19","author":"RJ Kang","year":"2010","unstructured":"Kang, R.J., McDiarmid, C.: The t-improper chromatic number of random graphs. Comb. Probab. Comput. 19(1), 87\u201398 (2010)","journal-title":"Comb. Probab. Comput."},{"issue":"8","key":"9_CR29","doi-asserted-by":"publisher","first-page":"1438","DOI":"10.1016\/j.disc.2007.07.070","volume":"308","author":"RJ Kang","year":"2008","unstructured":"Kang, R.J., M\u00fcller, T., Sereni, J.-S.: Improper colouring of (random) unit disk graphs. Discret. Math. 308(8), 1438\u20131454 (2008)","journal-title":"Discret. Math."},{"key":"9_CR30","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.ejc.2014.05.003","volume":"42","author":"J Kim","year":"2014","unstructured":"Kim, J., Kostochka, A.V., Zhu, X.: Improper coloring of sparse graphs with a given girth, I:(0, 1)-colorings of triangle-free graphs. Eur. J. Comb. 42, 26\u201348 (2014)","journal-title":"Eur. J. Comb."},{"issue":"4","key":"9_CR31","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1002\/jgt.21886","volume":"81","author":"J Kim","year":"2016","unstructured":"Kim, J., Kostochka, A.V., Zhu, X.: Improper coloring of sparse graphs with a given girth, II: constructions. J. Graph Theory 81(4), 403\u2013413 (2016)","journal-title":"J. Graph Theory"},{"issue":"3","key":"9_CR32","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"issue":"2","key":"9_CR33","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0095-8956(74)90063-X","volume":"16","author":"D Seinsche","year":"1974","unstructured":"Seinsche, D.: On a property of the class of n-colorable graphs. J. Comb. Theory Ser. B 16(2), 191\u2013193 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"9_CR34","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0166-218X(96)00094-7","volume":"69","author":"Y Jing-Ho","year":"1996","unstructured":"Jing-Ho, Y., Jer-Jeong, C., Chang, G.J.: Quasi-threshold graphs. Discret. Appl. Math. 69(3), 247\u2013255 (1996)","journal-title":"Discret. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68705-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T02:54:41Z","timestamp":1558320881000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68705-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319687049","9783319687056"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68705-6_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"2 November 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Eindhoven","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"43","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.win.tue.nl\/wg2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}