On induced subgraphs with odd degrees (Q1336646)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 681654
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On induced subgraphs with odd degrees |
scientific article; zbMATH DE number 681654 |
Statements
On induced subgraphs with odd degrees (English)
0 references
9 March 1995
0 references
The author proves that every graph \(G\) on \(n\) vertices with no isolated vertices contains an induced subgraph \(H\) such that every vertex in \(H\) has odd degree in \(H\) and \(| V(H) | \geq (1-o(1))\sqrt {n/6}\).
0 references
induced subgraph
0 references
odd degree
0 references
0.900550365447998
0 references
0.8763866424560547
0 references
0.8717308640480042
0 references
0.8525030612945557
0 references
