✦ LIBER ✦

Large induced degenerate subgraphs

✍ Scribed by N. Alon; J. Kahn; P. D. Seymour

Publisher: Springer Japan
Year: 1987
Tongue: English
Weight: 558 KB
Volume: 3
Category: Article
ISSN: 0911-0119
DOI: 10.1007/bf01788542

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Vertex partitions and maximum degenerate

Vertex partitions and maximum degenerate subgraphs

✍ Martín Matamala 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB

## Abstract Let __G__ be a graph with maximum degree __d__≥ 3 and ω(__G__)≤ __d__, where ω(__G__) is the __clique number__ of the graph __G__. Let __p__~1~ and __p__~2~ be two positive integers such that __d__ = __p__~1~ + __p__~2~. In this work, we prove that __G__ has a vertex partition __S__~1~,

Colorful induced subgraphs

✍ H.A. Kierstead; W.T. Trotter 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 302 KB

A colored graph is a graph whose vertices have been properly, though not necessarily optimally colored, with integers. Colored graphs have a natural orientation in which edges are directed from the end point with smaller color to the end point with larger color. A subgraph of a colored graph is colo

Sizes of graphs with induced subgraphs o

Sizes of graphs with induced subgraphs of large maximum degree

✍ Paul Erdős; Talmage James Reid; Richard Schelp; William Staton 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 249 KB

Graphs with n + k vertices in which every set of n +j vertices induce a subgraph of maximum degree at least n are considered. For j = 1 and for k fairly small compared to n, we determine the minimum number of edges in such graphs.

Stability for large forbidden subgraphs

✍ Vladimir Nikiforov 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB

## Abstract In this note we strengthen the stability theorem of Erdős and Simonovits. Write __K__~__r__~(__s__~1~, …, __s__~__r__~) for the complete __r__‐partite graph with classes of sizes __s__~1~, …, __s__~__r__~ and __T__~__r__~(__n__) for the __r__‐partite Turán graph of order __n__. Our main

Maximumk-regular induced subgraphs

✍ Domingos M. Cardoso; Marcin Kamiński; Vadim Lozin 📂 Article 📅 2007 🏛 Springer US 🌐 English ⚖ 291 KB

Every tree contains a large induced subg

Every tree contains a large induced subgraph with all degrees odd

✍ A.J. Radclife; A.D. Scott 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 222 KB

Caro et al. proved that every tree of order n contains an induced subgraph of order at least rn/2] with all degrees odd, and conjectured a better bound. In this note we prove that every tree of order n contains an induced subgraph of order at least 2L(n + 1)/3 .] with all degrees odd; this bound is