Recognition of unipolar and generalised split graphs

DOI10.3390/a8010046zbMath1461.05216arXiv1604.00922OpenAlexW1973229660MaRDI QIDQ1736638

Nikola Yolov, Colin J. H. McDiarmid

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.00922

zbMATH Keywords

representationsperfect graphsrecognition algorithmsunipolar graphsgeneralised split graphs

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs ⋮ Random perfect graphs ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around ⋮ Recognizing Graphs Close to Bipartite Graphs

Cites Work

• Algorithms for unipolar and generalized split graphs
• Solving partition problems with colour-bipartitions
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Recognizing Berge graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• Almost all Berge Graphs are Perfect
• Unnamed Item
• Unnamed Item

This page was built for publication: Recognition of unipolar and generalised split graphs