Graphs without a partition into two proportionally dense subgraphs

Cristina Bazgan, Janka Chlebíková, Clément Dallard

A \emph{proportionally dense subgraph} (PDS) is an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the s…