scientific article; zbMATH DE number 3959468
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).
- scientific article; zbMATH DE number 4065027
- scientific article; zbMATH DE number 4065028
- Publication:4865127
- scientific article; zbMATH DE number 540115
- Distinct degrees in induced subgraphs
- Subgraphs with large degrees and girth
- Subgraphs of minimal degree \(k\)
- Some new degree concepts in graphs
- Degree constrained subgraphs
- scientific article; zbMATH DE number 747033
- Forbidden graphs for degree and neighbourhood conditions
- Subgraphs of graphs. I
- Smaller subgraphs of minimum degree \(k\)
- Subdivisions of graphs with large minimum degree
- scientific article; zbMATH DE number 4065027 (Why is no real title available?)
- scientific article; zbMATH DE number 4065028 (Why is no real title available?)
- scientific article; zbMATH DE number 844142 (Why is no real title available?)
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)