{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T21:10:09Z","timestamp":1750972209371,"version":"3.41.0"},"publisher-location":"Cham","reference-count":46,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319687049"},{"type":"electronic","value":"9783319687056"}],"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_18","type":"book-chapter","created":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T06:06:22Z","timestamp":1509516382000},"page":"234-248","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Finding Cut-Vertices in the Square Roots of\u00a0a\u00a0Graph"],"prefix":"10.1007","author":[{"given":"Guillaume","family":"Ducoffe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,2]]},"reference":[{"issue":"P139","key":"18_CR1","first-page":"1","volume":"18","author":"A Adamaszek","year":"2011","unstructured":"Adamaszek, A., Adamaszek, M.: Uniqueness of graph square roots of girth six. Electron. J. Comb. 18(P139), 1 (2011)","journal-title":"Electron. J. Comb."},{"issue":"4","key":"18_CR2","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1137\/S0895480100367950","volume":"16","author":"G Agnarsson","year":"2003","unstructured":"Agnarsson, G., Halld\u00f3rsson, M.M.: Coloring powers of planar graphs. SIAM J. Discrete Math. 16(4), 651\u2013662 (2003)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"18_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(84)90073-8","volume":"8","author":"M Aigner","year":"1984","unstructured":"Aigner, M., Fromme, M.: A game of cops and robbers. Discrete Appl. Math. 8(1), 1\u201312 (1984)","journal-title":"Discrete Appl. Math."},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2014.05.030","volume":"177","author":"A Berry","year":"2014","unstructured":"Berry, A., Pogorelcnik, R., Simonet, G.: Organizing the atoms of the clique separator decomposition into an atom tree. Discrete Appl. Math. 177, 1\u201313 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"Part 1","key":"18_CR5","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.dam.2015.01.015","volume":"216","author":"H-L Bodlaender","year":"2017","unstructured":"Bodlaender, H.-L., Kratsch, S., Kreuzen, V., Kwon, O.-J., Ok, S.: Characterizing width two for variants of treewidth. Discrete Appl. Math. 216(Part 1), 29\u201346 (2017)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"18_CR6","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1002\/jgt.21782","volume":"77","author":"M Bonamy","year":"2014","unstructured":"Bonamy, M., L\u00e9v\u00eaque, B., Pinlou, A.: 2-distance coloring of sparse graphs. J. Graph Theory 77(3), 190\u2013218 (2014)","journal-title":"J. Graph Theory"},{"key":"18_CR7","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph Theory","author":"JA Bondy","year":"2008","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics. Springer, London (2008)"},{"issue":"1","key":"18_CR8","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. Comput. 31(1), 212\u2013232 (2001)","journal-title":"SIAM J. Comput."},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/11785293_38","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"M-S Chang","year":"2006","unstructured":"Chang, M.-S., Ko, M.-T., Lu, H.-I.: Linear-time algorithms for tree root problems. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 411\u2013422. Springer, Heidelberg (2006). doi: 10.1007\/11785293_38"},{"issue":"2","key":"18_CR10","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1007\/s00453-014-9967-4","volume":"74","author":"M Cochefert","year":"2016","unstructured":"Cochefert, M., Couturier, J.-F., Golovach, P.A., Kratsch, D., Paulusma, D.: Parameterized algorithms for finding square roots. Algorithmica 74(2), 602\u2013629 (2016)","journal-title":"Algorithmica"},{"key":"18_CR11","unstructured":"Ducoffe, G.: Finding cut-vertices in the square roots of a graph. Technical report hal-01477981, UCA, Inria, CNRS, I3S, France (2017). https:\/\/hal.archives-ouvertes.fr\/hal-01477981"},{"key":"18_CR12","unstructured":"Ducoffe, G., Coudert, D.: Clique-decomposition revisited. In: Revision (Research Report on HAL, hal-01266147) (2017)"},{"key":"18_CR13","unstructured":"Farzad, B., Karimi, M.: Square-root finding problem in graphs, a complete dichotomy theorem. Technical report, arXiv arXiv:1210.7684 (2012)"},{"issue":"1\u20132","key":"18_CR14","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/s00453-010-9442-9","volume":"62","author":"B Farzad","year":"2012","unstructured":"Farzad, B., Lau, L.C., Tuy, N.N.: Complexity of finding graph roots with girth conditions. Algorithmica 62(1\u20132), 38\u201353 (2012)","journal-title":"Algorithmica"},{"issue":"1","key":"18_CR15","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0095-8956(74)90091-4","volume":"16","author":"H Fleischner","year":"1974","unstructured":"Fleischner, H.: The square of every two-connected graph is Hamiltonian. J. Comb. Theory Ser. B 16(1), 29\u201334 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"key":"18_CR16","first-page":"3","volume":"7","author":"T Gallai","year":"1962","unstructured":"Gallai, T.: Graphen mit triangulierbaren ungeraden Vielecken. Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl 7, 3\u201336 (1962)","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl"},{"key":"18_CR17","doi-asserted-by":"publisher","unstructured":"Golovach, P., Heggernes, P., Kratsch, D., Lima, P., Paulusma, D.: Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. In: Bodlaender, H.L., Woeginger, G.J. (eds.) WG 2017. LNCS, vol. 10520, pp. 275\u2013288. Springer, Cham (2017). doi: 10.1007\/978-3-319-68705-6_z . arXiv:1703.05102","DOI":"10.1007\/978-3-319-68705-6_z"},{"key":"18_CR18","unstructured":"Golovach, P., Kratsch, D., Paulusma, D., Stewart, A.: A linear kernel for finding square roots of almost planar graphs. In: SWAT, pp. 4:1\u20134:14 (2016)"},{"key":"18_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-319-44543-4_28","volume-title":"Combinatorial Algorithms","author":"PA Golovach","year":"2016","unstructured":"Golovach, P.A., Kratsch, D., Paulusma, D., Stewart, A.: Finding cactus roots in polynomial time. In: M\u00e4kinen, V., Puglisi, S.J., Salmela, L. (eds.) IWOCA 2016. LNCS, vol. 9843, pp. 361\u2013372. Springer, Cham (2016). doi: 10.1007\/978-3-319-44543-4_28"},{"key":"18_CR20","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, vol. 57. Elsevier, Amsterdam (2004)"},{"issue":"3","key":"18_CR21","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/0196-6774(88)90023-5","volume":"9","author":"MC Golumbic","year":"1988","unstructured":"Golumbic, M.C., Hammer, P.L.: Stability in circular arc graphs. J. Algorithms 9(3), 314\u2013320 (1988)","journal-title":"J. Algorithms"},{"issue":"4","key":"18_CR22","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/S0021-9800(67)80050-4","volume":"2","author":"F Harary","year":"1967","unstructured":"Harary, F., Karp, R.M., Tutte, W.T.: A criterion for planarity of the square of a graph. J. Comb. Theory 2(4), 395\u2013405 (1967)","journal-title":"J. Comb. Theory"},{"issue":"3","key":"18_CR23","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","volume":"306","author":"P Heggernes","year":"2006","unstructured":"Heggernes, P.: Minimal triangulations of graphs: a survey. Discrete Math. 306(3), 297\u2013317 (2006)","journal-title":"Discrete Math."},{"issue":"6","key":"18_CR24","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372\u2013378 (1973)","journal-title":"Commun. ACM"},{"issue":"2","key":"18_CR25","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1145\/1150334.1150337","volume":"2","author":"LC Lau","year":"2006","unstructured":"Lau, L.C.: Bipartite roots of graphs. ACM Trans. Algorithms (TALG) 2(2), 178\u2013208 (2006)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"1","key":"18_CR26","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/S0895480103425930","volume":"18","author":"LC Lau","year":"2004","unstructured":"Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split, and chordal graphs. SIAM J. Discrete Math. 18(1), 83\u2013102 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"18_CR27","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.ipl.2010.11.003","volume":"111","author":"VB Le","year":"2011","unstructured":"Le, V.B., Nguyen, N.T.: A good characterization of squares of strongly chordal split graphs. Inf. Process. Lett. 111(3), 120\u2013123 (2011)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"18_CR28","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1016\/j.disc.2009.09.004","volume":"310","author":"VB Le","year":"2010","unstructured":"Le, V.B., Tuy, N.N.: The square of a block graph. Discrete Math. 310(4), 734\u2013741 (2010)","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"18_CR29","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0012-365X(93)90510-Z","volume":"113","author":"H-G Leimer","year":"1993","unstructured":"Leimer, H.-G.: Optimal decomposition by clique separators. Discrete Math. 113(1\u20133), 99\u2013123 (1993)","journal-title":"Discrete Math."},{"issue":"1","key":"18_CR30","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0012-365X(03)00059-1","volume":"269","author":"K-W Lih","year":"2003","unstructured":"Lih, K.-W., Wang, W.-F., Zhu, X.: Coloring the square of a $${K}_4$$ K 4 -minor free graph. Discrete Math. 269(1), 303\u2013309 (2003)","journal-title":"Discrete Math."},{"issue":"7","key":"18_CR31","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1016\/j.dam.2010.03.012","volume":"159","author":"MC Lin","year":"2011","unstructured":"Lin, M.C., Rautenbach, D., Soulignac, F.J., Szwarcfiter, J.L.: Powers of cycles, powers of paths, and distance graphs. Discrete Appl. Math. 159(7), 621\u2013627 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"18_CR32","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/S089548019120016X","volume":"8","author":"Y-L Lin","year":"1995","unstructured":"Lin, Y.-L., Skiena, S.S.: Algorithms for square roots of graphs. SIAM J. Discrete Math. 8(1), 99\u2013118 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"18_CR33","doi-asserted-by":"crossref","unstructured":"Lloyd, E., Ramanathan, S.: On the complexity of distance-2 coloring. In: ICCI, pp. 71\u201374. IEEE (1992)","DOI":"10.1109\/ICCI.1992.227702"},{"issue":"10","key":"18_CR34","doi-asserted-by":"publisher","first-page":"1538","DOI":"10.1016\/j.dam.2012.12.027","volume":"161","author":"M Milani\u010d","year":"2013","unstructured":"Milani\u010d, M., Schaudt, O.: Computing square roots of trivially perfect and threshold graphs. Discrete Appl. Math. 161(10), 1538\u20131545 (2013)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"18_CR35","doi-asserted-by":"publisher","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 bound on the chromatic number of the square of a planar graph. J. Comb. Theory Ser. B 94(2), 189\u2013213 (2005)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"18_CR36","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0166-218X(94)00023-9","volume":"54","author":"R Motwani","year":"1994","unstructured":"Motwani, R., Sudan, M.: Computing roots of graphs is hard. Discrete Appl. Math. 54(1), 81\u201388 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"18_CR37","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/S0021-9800(67)80030-9","volume":"2","author":"A Mukhopadhyay","year":"1967","unstructured":"Mukhopadhyay, A.: The square root of a graph. J. Comb. Theory 2(3), 290\u2013295 (1967)","journal-title":"J. Comb. Theory"},{"key":"18_CR38","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.dam.2013.05.026","volume":"168","author":"NV Nestoridis","year":"2014","unstructured":"Nestoridis, N.V., Thilikos, D.M.: Square roots of minor closed graph classes. Discrete Appl. Math. 168, 34\u201339 (2014)","journal-title":"Discrete Appl. Math."},{"key":"18_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/978-3-319-12340-0_30","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"VB Le","year":"2014","unstructured":"Le, V.B., Oversberg, A., Schaudt, O.: Polynomial time recognition of squares of ptolemaic graphs and 3-sun-free split graphs. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 360\u2013371. Springer, Cham (2014). doi: 10.1007\/978-3-319-12340-0_30"},{"issue":"1\u20133","key":"18_CR40","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0166-218X(97)00041-3","volume":"79","author":"A Parra","year":"1997","unstructured":"Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discrete Appl. Math. 79(1\u20133), 171\u2013188 (1997)","journal-title":"Discrete Appl. Math."},{"key":"18_CR41","first-page":"307","volume":"9","author":"B Randerath","year":"1994","unstructured":"Randerath, B., Volkmann, L.: A characterization of well covered block-cactus graphs. Australas. J. Comb. 9, 307\u2013314 (1994)","journal-title":"Australas. J. Comb."},{"issue":"3","key":"18_CR42","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.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"issue":"3","key":"18_CR43","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1002\/j.1538-7305.1960.tb03936.x","volume":"39","author":"IC Ross","year":"1960","unstructured":"Ross, I.C., Harary, F.: The square of a tree. Bell Syst. Tech. J. 39(3), 641\u2013647 (1960)","journal-title":"Bell Syst. Tech. J."},{"issue":"2","key":"18_CR44","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55(2), 221\u2013232 (1985)","journal-title":"Discrete Math."},{"issue":"6","key":"18_CR45","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1090\/S0002-9904-1970-12628-3","volume":"76","author":"A Tucker","year":"1970","unstructured":"Tucker, A.: Characterizing circular-arc graphs. Bull. Am. Math. Soc. 76(6), 1257\u20131260 (1970)","journal-title":"Bull. Am. Math. Soc."},{"key":"18_CR46","unstructured":"Wegner, G.: Graphs with given diameter and a coloring problem. University of Dortmund, Technical report (1977)"}],"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_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T20:35:09Z","timestamp":1750970109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68705-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319687049","9783319687056"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68705-6_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"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"}}]}}