{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T22:01:43Z","timestamp":1767909703924,"version":"3.49.0"},"reference-count":9,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2015,2,13]],"date-time":"2015-02-13T00:00:00Z","timestamp":1423785600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A graph is unipolar if it can be partitioned into a clique and a disjoint union of cliques, and a graph is a generalised split graph if it or its complement is unipolar. A unipolar partition of a graph can be used to find efficiently the clique number, the stability number, the chromatic number, and to solve other problems that are hard for general graphs. We present an O(n2)-time algorithm for recognition of n-vertex generalised split graphs, improving on previous O(n3)-time algorithms.<\/jats:p>","DOI":"10.3390\/a8010046","type":"journal-article","created":{"date-parts":[[2015,2,13]],"date-time":"2015-02-13T10:40:07Z","timestamp":1423824007000},"page":"46-59","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Recognition of Unipolar and Generalised Split Graphs"],"prefix":"10.3390","volume":"8","author":[{"given":"Colin","family":"McDiarmid","sequence":"first","affiliation":[{"name":"Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikola","family":"Yolov","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX 13QD, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2015,2,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1017\/S0963548300000079","article-title":"Almost all Berge graphs are perfect","volume":"1","author":"Steger","year":"1992","journal-title":"Comb. Probab. Comput."},{"key":"ref_2","unstructured":"Cornu\u00e9jols, G., Liu, X., and Vu\u0161kovi\u0107, K. (2013, January 26\u201329). A polynomial algorithm for recognizing perfect graphs, Berkeley, CA, USA."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","article-title":"Recognizing Berge graphs","volume":"25","author":"Chudnovsky","year":"2005","journal-title":"Combinatorica"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/S0304-0208(08)72943-8","article-title":"Polynomial algorithms for perfect graphs","volume":"88","author":"Schrijver","year":"1984","journal-title":"North-Holl. Math. Stud."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.dam.2013.08.011","article-title":"Algorithms for unipolar and generalized split graphs","volume":"162","author":"Eschen","year":"2014","journal-title":"Discrete Appl. Math."},{"key":"ref_6","first-page":"16","article-title":"Algorithms for the canonical decomposition of a graph and recognizing polarity","volume":"6","author":"Tyshkevich","year":"1985","journal-title":"Izvestia Akad. Nauk BSSR Ser. Fiz.-Mat. Nauk"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/s00373-012-1270-z","article-title":"Solving partition problems with colour-bipartitions","volume":"30","author":"Churchley","year":"2014","journal-title":"Graphs Comb."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1137\/0205048","article-title":"On the complexity of timetable and multicommodity flow problems","volume":"5","author":"Even","year":"1976","journal-title":"SIAM J. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","article-title":"A linear-time algorithm for testing the truth of certain quantified boolean formulas","volume":"8","author":"Aspvall","year":"1979","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/1\/46\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:42:42Z","timestamp":1760215362000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/1\/46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,13]]},"references-count":9,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2015,3]]}},"alternative-id":["a8010046"],"URL":"https:\/\/doi.org\/10.3390\/a8010046","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,13]]}}}