Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-24T05:16:15.106Z Has data issue: false hasContentIssue false
  • English
  • Français

Large Induced Subgraphs with All Degrees Odd

Published online by Cambridge University Press:  12 September 2008

A. D. Scott
A. D. Scott
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, England
Get access Rights & Permissions [Opens in a new window]

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 cis a constant. We also give a bound in terms of chromatic number, and resolve the analogous problem for random graphs.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 4 , December 1992 , pp. 335 - 349
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bollobás, B. (1979) Graph Theory, An Introductory Course, Springer-Verlag, New York, Heidelberg, Berlin180.Google Scholar
[2]Caro, Y. (to appear) On induced subgraphs with odd degrees.Google Scholar
[3]Caro, Y., Krasikov, I. and Roditty, Y. (to appear) On induced subgraphs of trees with restricted degrees. Discrete Mathematics.Google Scholar
[4]Lovász, L. (1979) Combinatorial Problems and Exercises, North-Holland, Amsterdam, 551.Google Scholar
[5]Radcliffe, A. J. and Scott, A. D. (submitted) Every tree has a large induced subgraph with all degrees odd.Google Scholar