4 papers
Blocker size via matching minors
Nikola Yolov
Finding the maximum number of maximal independent sets in an -vertex graph , , from a restricted class is an extensively studied problem. Let denote the matching…
Hamilton cycles, minimum degree and bipartite holes
Colin McDiarmid, Nikola Yolov
We present a tight extremal threshold for the existence of Hamilton cycles in graphs with large minimum degree and without a large ``bipartite hole`` (two disjoint sets of vertices…
Polarity and Monopolarity of -colourable comparability graphs
Nikola Yolov
We sharpen the result that polarity and monopolarity are NP-complete problems by showing that they remain NP-complete if the input graph is restricted to be a -colourable compar…
Recognition of unipolar and generalised split graphs
Colin McDiarmid, Nikola Yolov
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…