{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T18:58:33Z","timestamp":1778871513723,"version":"3.51.4"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030002558","type":"print"},{"value":"9783030002565","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-030-00256-5_21","type":"book-chapter","created":{"date-parts":[[2018,9,1]],"date-time":"2018-09-01T08:22:08Z","timestamp":1535790128000},"page":"252-265","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Perfect Linegraph Squares"],"prefix":"10.1007","author":[{"given":"Meike","family":"Hatzel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Wiederrecht","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,2]]},"reference":[{"issue":"4","key":"21_CR1","doi-asserted-by":"publisher","first-page":"2081","DOI":"10.1007\/s11277-016-3362-1","volume":"94","author":"IA Arputhamary","year":"2017","unstructured":"Arputhamary, I.A., Mercy, M.H.: An analytical discourse on strong edge coloring for interference-free channel assignment in interconnection networks. Wirel. Pers. Commun. 94(4), 2081\u20132094 (2017)","journal-title":"Wirel. Pers. Commun."},{"issue":"1\u20133","key":"21_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0166-218X(92)90275-F","volume":"24","author":"K Cameron","year":"1989","unstructured":"Cameron, K.: Induced matchings. Discret. Appl. Math. 24(1\u20133), 97\u2013102 (1989)","journal-title":"Discret. Appl. Math."},{"issue":"1\u20133","key":"21_CR3","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0012-365X(02)00803-8","volume":"266","author":"K Cameron","year":"2003","unstructured":"Cameron, K., Sritharan, R., Tang, Y.: Finding a maximum induced matching in weakly chordal graphs. Discret. Math. 266(1\u20133), 133\u2013142 (2003)","journal-title":"Discret. Math."},{"key":"21_CR4","doi-asserted-by":"publisher","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, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"21_CR5","first-page":"1","volume":"121","author":"M Chudnovsky","year":"2016","unstructured":"Chudnovsky, M., Scott, A., Seymour, P.: Induced subgraphs of graphs with large chromatic number. iii. long holes. Combinatorica 121, 1\u201316 (2016)","journal-title":"Combinatorica"},{"key":"21_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, vol. 5. Springer, Heildelberg (2010)"},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0304-0208(08)72924-4","volume":"88","author":"P Duchet","year":"1984","unstructured":"Duchet, P.: Classical perfect graphs: an introduction with emphasis on triangulated and interval graphs. North-Holland Math. Stud. 88, 67\u201396 (1984)","journal-title":"North-Holland Math. Stud."},{"issue":"23","key":"21_CR8","doi-asserted-by":"publisher","first-page":"2513","DOI":"10.1016\/j.tcs.2010.10.043","volume":"412","author":"J Fiala","year":"2011","unstructured":"Fiala, J., Golovach, P.A., Kratochv\u00edl, J.: Parameterized complexity of coloring problems: treewidth versus vertex cover. Theor. Comput. Sci. 412(23), 2513\u20132523 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"21_CR9","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/(SICI)1097-0118(199704)24:4<323::AID-JGT4>3.0.CO;2-Q","volume":"24","author":"C Flotow","year":"1997","unstructured":"Flotow, C.: Graphs whose powers are chordal and graphs whose powers are interval graphs. J. Graph Theory 24(4), 323\u2013330 (1997)","journal-title":"J. Graph Theory"},{"issue":"3\u20134","key":"21_CR10","doi-asserted-by":"publisher","first-page":"413","DOI":"10.4064\/am-19-3-4-413-441","volume":"19","author":"A Gy\u00e1rf\u00e1s","year":"1987","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Applicationes Mathematicae 19(3\u20134), 413\u2013441 (1987)","journal-title":"Applicationes Mathematicae"},{"issue":"1","key":"21_CR11","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1016\/S0304-3975(00)00388-1","volume":"262","author":"J Janssen","year":"2001","unstructured":"Janssen, J., Narayanan, L.: Approximation algorithms for channel assignment with constraints. Theor. Comput. Sci. 262(1), 649\u2013667 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR12","unstructured":"Ko, C., Shepherd, F.: Adding an identity to a totally unimodular matrix (1994)"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Lloyd, E.L., Ramanathan, S.: On the complexity of distance-2 coloring. In: Proceedings of the Fourth International Conference on Computing and Information, ICCI 1992, pp. 71\u201374. IEEE (1992)","DOI":"10.1109\/ICCI.1992.227702"},{"issue":"3","key":"21_CR14","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0166-218X(01)00237-2","volume":"118","author":"M Mahdian","year":"2002","unstructured":"Mahdian, M.: On the computational complexity of strong edge coloring. Discret. Appl. Math. 118(3), 239\u2013248 (2002)","journal-title":"Discret. Appl. Math."},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Nandagopal, T., Kim, T.E., Gao, X., Bharghavan, V.: Achieving MAC layer fairness in wireless packet networks. In: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, pp. 87\u201398. ACM (2000)","DOI":"10.1145\/345910.345925"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Ramanathan, S.: A unified framework and algorithm for (T\/F\/C) DMA channel assignment in wireless networks. In: INFOCOM 1997, Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, Proceedings IEEE, vol. 2, pp. 900\u2013907. IEEE (1997)","DOI":"10.1109\/INFCOM.1997.644573"},{"issue":"2","key":"21_CR17","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1109\/90.222924","volume":"1","author":"S Ramanathan","year":"1993","unstructured":"Ramanathan, S., Lloyd, E.L.: Scheduling algorithms for multihop radio networks. IEEE\/ACM Trans. Netw. (TON) 1(2), 166\u2013177 (1993)","journal-title":"IEEE\/ACM Trans. Netw. (TON)"},{"issue":"1","key":"21_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-003-0540-1","volume":"20","author":"B Randerath","year":"2004","unstructured":"Randerath, B., Schiermeyer, I.: Vertex colouring and forbidden subgraphs-a survey. Graphs Combin. 20(1), 1\u201340 (2004)","journal-title":"Graphs Combin."},{"key":"21_CR19","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/j.dam.2018.02.013","volume":"243","author":"R Scheidweiler","year":"2018","unstructured":"Scheidweiler, R., Wiederrecht, S.: On chordal graph and line graph squares. Discret. Appl. Math. 243, 239\u2013247 (2018)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"21_CR20","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":"1","key":"21_CR21","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","volume":"15","author":"LJ Stockmeyer","year":"1982","unstructured":"Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett. 15(1), 14\u201319 (1982)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-00256-5_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T19:34:35Z","timestamp":1751830475000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-00256-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030002558","9783030002565"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-00256-5_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"2 September 2018","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":"Cottbus","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"44","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.wg2018.b-tu.de\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"66","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"45% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"11,5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}