{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:22:20Z","timestamp":1787322140100,"version":"build-2736575974"},"reference-count":11,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2011,1,1]]},"abstract":"<jats:p>A graph is polar if its vertex set can be partitioned into [Formula: see text] and [Formula: see text] in such a way that [Formula: see text] induces a complete multipartite graph and [Formula: see text] induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite, cobipartite, and split graphs. The problem of recognizing polar graphs is NP-complete in general. However, it has been shown to be polynomial for several classes of graphs, including cographs and chordal graphs. In this paper, we study the problem of recognizing graphs whose line graphs are polar. It turns out that the core part of this problem lies in determining whether the edge set of a graph admits a partition [Formula: see text] so that [Formula: see text] induces a [Formula: see text]-free subgraph (i.e., a matching) and [Formula: see text] induces a [Formula: see text]-free subgraph. We give a structural characterization of such graphs. The characterization enables us to devise an [Formula: see text] time algorithm to solve the stated recognition problem.<\/jats:p>","DOI":"10.1137\/100789208","type":"journal-article","created":{"date-parts":[[2011,8,25]],"date-time":"2011-08-25T18:32:23Z","timestamp":1314297143000},"page":"1269-1284","source":"Crossref","is-referenced-by-count":9,"title":["Line-Polar Graphs: Characterization and Recognition"],"prefix":"10.1137","volume":"25","author":[{"given":"Ross","family":"Churchley","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,8,25]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(86)90113-5"},{"key":"R2","unstructured":"R. Churchley and J. Huang, Polarity and Monopolarity of Claw-Free Graphs, manuscript, 2010."},{"key":"R3","unstructured":"T. Ekim, Polarity of Claw-Free Graphs, manuscript, 2009."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"T. Ekim, P. Heggernes and D. Meister, Polar permutation graphs, in\n                      Proceedings of IWOCA 2009\n                      , Lecture Notes in Comput. Sci. 5874, J. Fiala, J. Kratochvil and M. Miller, eds. Springer, Berlin, 2009, pp.\u00a0218\u2013229.","DOI":"10.1007\/978-3-642-10217-2_23"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.01.026"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.05.019"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.08.025"},{"key":"R8","doi-asserted-by":"crossref","DOI":"10.37236\/1799","volume":"11","author":"Farrugia A.","year":"2004","journal-title":"Electron. J. Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/1077-8926","issn-type":"print"},{"key":"R9","first-page":"311","author":"Foldes S.","year":"1977","journal-title":"Proceedings of the 8th South-Eastern Conference on Combinatorics, Graph Theory and Computing"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.12.012"},{"key":"R11","unstructured":"D. West,\n                      Introduction to Graph Theory\n                      , 2nd ed., Prentice-Hall, Englewood Cliffs, NJ, 2001."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100789208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:18:36Z","timestamp":1787318316000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100789208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,1]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,1,1]]}},"alternative-id":["10.1137\/100789208"],"URL":"https:\/\/doi.org\/10.1137\/100789208","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,1]]}}}