E. Popova

On the Minimum Possible Maximum Degree of Induced Subgraphs of Product Graphs

The following is a natural and fundamental question for a graph $G$: if an induced subgraph $H$ of $G$ has $x$ more vertices than a maximum independent set, what can be said about the maximum degree of $H$ as a function of $x$? The case $x=1$ is already of considerable interest. For example, in his celebrated proof of...