scientific article; zbMATH DE number 3959468

From MaRDI portal
Publication:3728027





This paper concerns the question: given a graph on p vertices with minimum degree q, can one always find a subgraph having r vertices with minimum degree at least s? It contains the following main results, and discussions of their consequences and one other result: 1. If a graph on r vertices is m-colorable, its minimum degree cannot be more than (m-1)r/m; and there is an m-colorable graph if \(q\Leftarrow (m- 1)p/m\). Thus if s exceeds for former quantity and q obeys the latter condition, the conclusion cannot follow. 2. If the number of ways of picking one vertex, fewer than s of its first q neighbors, and the remaining of r total vertices from the rest is less than the number of r element subsets of the p vertices, then the question must have an affirmative answer. 3. We can always pick out \(p/(q(q-1)+1)\) vertices the removal of which reduces the maximum degree by at most one, to at least 2-1. (Choose a vertex of degree q and remove t, its degree q neighbors and their neighbors; and repeat this process until one has the requisite number of vertices. 4. If p is \(a+b\) and q is \(c+d\), then either there is a graph on a vertices of minimum degree c or one on b vertices with minimum degree d. (If one divides the p vertices into parts of size a and b so that there are fewest edges between, one of the parts obeys this condition, else switching will reduce the number of edges between).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3728027)