{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T09:49:01Z","timestamp":1742982541691,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662535356"},{"type":"electronic","value":"9783662535363"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53536-3_10","type":"book-chapter","created":{"date-parts":[[2016,9,27]],"date-time":"2016-09-27T12:39:25Z","timestamp":1474979965000},"page":"109-120","source":"Crossref","is-referenced-by-count":2,"title":["Exhaustive Generation of k-Critical $${\\mathcal H}$$ -Free Graphs"],"prefix":"10.1007","author":[{"given":"Jan","family":"Goedgebeur","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Schaudt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,28]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1002\/jgt.10161","volume":"45","author":"T B\u00f6hme","year":"2004","unstructured":"B\u00f6hme, T., Mohar, B., \u0160krekovski, R., Stiebitz, M.: Subdivisions of large complete bipartite graphs and long induced paths in \n            $$k$$\n          -connected graphs. J. Graph Theor. 45, 270\u2013274 (2004)","journal-title":"J. Graph Theor."},{"issue":"2","key":"10_CR2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.7155\/jgaa.00091","volume":"8","author":"JM Boyer","year":"2004","unstructured":"Boyer, J.M., Myrvold, W.J.: On the cutting edge: simplified \n            $$O(n)$$\n           planarity by edge addition. J. Graph Algorithms. Appl. 8(2), 241\u2013273 (2004)","journal-title":"J. Graph Algorithms. Appl."},{"issue":"1\u20132","key":"10_CR3","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/j.dam.2012.07.018","volume":"161","author":"G Brinkmann","year":"2013","unstructured":"Brinkmann, G., Coolsaet, K., Goedgebeur, J., M\u00e9lot, H.: House of graphs: a database of interesting graphs. Discrete Appl. Math. 161(1\u20132), 311\u2013314 (2013). \nhttp:\/\/hog.grinvin.org\/","journal-title":"Discrete Appl. Math."},{"key":"10_CR4","first-page":"40","volume":"32","author":"G Brinkmann","year":"1997","unstructured":"Brinkmann, G., Meringer, M.: The smallest 4-regular 4-chromatic graphs with girth 5. Graph Theor. Notes New York 32, 40\u201341 (1997)","journal-title":"Graph Theor. Notes New York"},{"key":"10_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1007\/978-3-642-10631-6_61","volume-title":"Algorithms and computation","author":"D Bruce","year":"2009","unstructured":"Bruce, D., Ho\u00e0ng, C.T., Sawada, J.: A certifying algorithm for 3-colorability of P\n          \n            $$_\\text{5 }$$\n          -free graphs. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 594\u2013604. Springer, Heidelberg (2009)"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Chudnovsky, M., Goedgebeur, J., Schaudt, O., Zhong, M.: Obstructions for three-coloring graphs with one forbidden induced subgraph. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, 10\u201312 January 2016, Arlington, VA, USA, pp. 1774\u20131783 (2016)","DOI":"10.1137\/1.9781611974331.ch123"},{"issue":"04","key":"10_CR7","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1017\/S0963548398003678","volume":"7","author":"T Emden-Weinert","year":"1998","unstructured":"Emden-Weinert, T., Hougardy, S., Kreuter, B.: Uniquely colourable graphs and the hardness of colouring graphs of large girth. Comb. Probab. Comput. 7(04), 375\u2013386 (1998)","journal-title":"Comb. Probab. Comput."},{"key":"10_CR8","unstructured":"Goedgebeur, J.: Homepage of generator for 4-critical \n            $$P_t$$\n          -free graphs. \nhttp:\/\/caagt.ugent.be\/criticalpfree\/"},{"key":"10_CR9","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.dam.2013.12.008","volume":"167","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Paulusma, D., Song, J.: Coloring graphs without short cycles and long induced paths. Discrete Appl. Math. 167, 107\u2013120 (2014)","journal-title":"Discrete Appl. Math."},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1007\/978-3-642-54423-1_47","volume-title":"latin 2014: theoretical informatics","author":"P Hell","year":"2014","unstructured":"Hell, P., Huang, S.: Complexity of coloring graphs without paths and cycles. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 538\u2013549. Springer, Heidelberg (2014)"},{"key":"10_CR11","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.dam.2014.06.007","volume":"182","author":"CT Ho\u00e0ng","year":"2015","unstructured":"Ho\u00e0ng, C.T., Moore, B., Recoskie, D., Sawada, J., Vatshelle, M.: Constructions of \n            $$k$$\n          -critical \n            $${P}_5$$\n          -free graphs. Discrete Appl. Math. 182, 91\u201398 (2015)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"10_CR12","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"10_CR13","first-page":"61","volume":"2","author":"M Kami\u0144ski","year":"2007","unstructured":"Kami\u0144ski, M., Lozin, V.V.: Coloring edges and vertices of graphs without short or long cycles. Contrib. Discrete Math. 2, 61\u201366 (2007)","journal-title":"Contrib. Discrete Math."},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1007\/3-540-45477-2_23","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D Kr\u00e1l\u2019","year":"2001","unstructured":"Kr\u00e1l\u2019, D., Kratochv\u00edl, J., Tuza, Z., Woeginger, G.J.: Complexity of Coloring Graphs without Forbidden Induced Subgraphs. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 254\u2013262. \u00a0Springer, Heidelberg (2001)"},{"issue":"1","key":"10_CR15","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"D Leven","year":"1983","unstructured":"Leven, D., Galil, Z.: NP completeness of finding the chromatic index of regular graphs. J. Algorithms 4(1), 35\u201344 (1983)","journal-title":"J. Algorithms"},{"key":"10_CR16","doi-asserted-by":"crossref","first-page":"1682","DOI":"10.1137\/110829222","volume":"26","author":"F Maffray","year":"2012","unstructured":"Maffray, F., Morel, G.: On 3-colorable \n            $${P}_5$$\n          -free graphs. SIAM J. Discrete Math. 26, 1682\u20131708 (2012)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"10_CR17","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1006\/jagm.1997.0898","volume":"26","author":"BD McKay","year":"1998","unstructured":"McKay, B.D.: Isomorph-free exhaustive generation. J. Algorithms 26(2), 306\u2013324 (1998)","journal-title":"J. Algorithms"},{"key":"10_CR18","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","volume":"60","author":"BD McKay","year":"2014","unstructured":"McKay, B.D., Piperno, A.: Practical graph isomorphism II. J. Symbolic Comput. 60, 94\u2013112 (2014)","journal-title":"J. Symbolic Comput."},{"issue":"2","key":"10_CR19","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0166-218X(03)00446-3","volume":"136","author":"B Randerath","year":"2004","unstructured":"Randerath, B., Schiermeyer, I.: 3-colorability \n            $$\\in $$\n           P for \n            $${P}_6$$\n          -free graphs. Discrete Appl. Math. 136(2), 299\u2013313 (2004)","journal-title":"Discrete Appl. Math."},{"key":"10_CR20","first-page":"557","volume-title":"Theory and Applications of Graphs","author":"DP Sumner","year":"1981","unstructured":"Sumner, D.P.: Subtrees of a graph and the chromatic number. In: Chartrand, G. (ed.) Theory and Applications of Graphs, pp. 557\u2013576. John Wiley, New York (1981)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53536-3_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,7]],"date-time":"2017-06-07T05:04:20Z","timestamp":1496811860000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53536-3_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662535356","9783662535363"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53536-3_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}