Large Induced Subgraphs with All Degrees Odd

A. D. Scott

Source record

Source: Crossref

Published: Dec 1, 1992

DOI: 10.1017/s0963548300000389

Open original source ↗

Source abstract

We prove that every connected graph of order n ≥ 2 has an induced subgraph with all degrees odd of order at least cn /log n , where c is a constant. We also give a bound in terms of chromatic number, and resolve the analogous problem for random graphs.

Evidence graph

No public relationships recorded yet.

Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.