𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Extremal problems for chromatic neighborhood sets

✍ Scribed by André Kündgen; Michael Molloy

Publisher
John Wiley and Sons
Year
2002
Tongue
English
Weight
79 KB
Volume
40
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The chromatic neighborhood sequence of a graph G is the list of the chromatic numbers of the subgraphs induced by the neighborhoods of the vertices. We study the maximum multiplicity of this sequence, proving, amongst other things, that if a chromatic neighborhood sequence has t distinct values, the largest value being d~t~, then there is a value with multiplicity at least ${2d_t \over t}(1-\Theta(\ln\ t/t))$. This bound is asymptotically tight. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 68–74, 2002

📜 SIMILAR VOLUMES

Chromatic neighborhood sets
Chromatic neighborhood sets
✍ Molloy, Michael 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 242 KB

For each vertex v in a graph G, we denote by χ v the chromatic number of the subgraph induced by its neighborhood, and we set χ N (G) = {χ v : v ∈ V (G)}. We characterize those sets X for which there exists some G of prescribed size with X = χ N (G), and prove a related conjecture of Fajtlowicz. We

Extremal problems involving neighborhood
Extremal problems involving neighborhood unions
✍ Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Richard H. Schelp 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB

We examine several extremal problems for graphs satisfying the property JN(x) u N(y)l ? s f o r every pair of nonadjacent vertices x , y E V ( G ) . In particular, values for s are found that ensure that the graph contains an s-matching, a 1-factor, a path of a specific length, or a cycle of a spec

Extremal Problems for Sets Forming Boole
Extremal Problems for Sets Forming Boolean Algebras and Complete Partite Hypergraphs
✍ David S. Gunderson; Vojtěch Rödl; Alexander Sidorenko 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 209 KB

Three classes of finite structures are related by extremal properties: complete d-partite d-uniform hypergraphs, d-dimensional affine cubes of integers, and families of 2 d sets forming a d-dimensional Boolean algebra. We review extremal results for each of these classes and derive new ones for Bool

Extremal results for rooted minor proble
Extremal results for rooted minor problems
✍ Leif K Jørgensen; Ken-ichi Kawarabayashi 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

## Abstract In this article, we consider the following problem. Given four distinct vertices __v__~1~,__v__~2~,__v__~3~,__v__~4~. How many edges guarantee the existence of seven connected disjoint subgraphs __X__~i~ for __i__ = 1,…, 7 such that __X__~j~ contains __v__~j~ for __j__ = 1, 2, 3, 4 and