𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Decomposing large graphs with small graphs of high density

✍ Scribed by Yuster, Raphael

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
146 KB
Volume
32
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that for every positive integer h, and for every > 0, there are graphs H = (V H , E H ) with at least h vertices and with density at least 0.5with the following property:

any graph with minimum degree at least |V G | 2 (1 + o(1)) and |E H | divides |E G |, then G has an H-decomposition. This result extends the results of [

πŸ“œ SIMILAR VOLUMES

Extremal graphs with bounded densities o
Extremal graphs with bounded densities of small subgraphs
✍ Griggs, Jerrold R.; Simonovits, MiklοΏ½os; Thomas, George Rubin πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 373 KB

Let Ex(n, k, Β΅) denote the maximum number of edges of an n-vertex graph in which every subgraph of k vertices has at most Β΅ edges. Here we summarize some known results of the problem of determining Ex(n, k, Β΅), give simple proofs, and find some new estimates and extremal graphs. Besides proving new

Total colorings of planar graphs with la
Total colorings of planar graphs with large maximum degree
✍ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 97 KB πŸ‘ 2 views

It is proved that a planar graph with maximum degree βˆ† β‰₯ 11 has total (vertex-edge) chromatic number βˆ† + 1.

(2 + ?)-Coloring of planar graphs with l
(2 + ?)-Coloring of planar graphs with large odd-girth
✍ Klostermeyer, William; Zhang, Cun Quan πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 258 KB πŸ‘ 2 views

The odd-girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function f ( ) for each : 0 < < 1 such that, if the odd-girth of a planar graph G is at least f ( ), then G is (2 + )-colorable. N

The circular chromatic number of series-
The circular chromatic number of series-parallel graphs with large girth
✍ Chien, Chihyun; Zhu, Xuding πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 213 KB πŸ‘ 2 views

It was proved by Hell and Zhu that, if G is a series-parallel graph of girth at least 2 (3k -1)/2 , then Ο‡ c (G) ≀ 4k/(2k -1). In this article, we prove that the girth requirement is sharp, i.e., for any k β‰₯ 2, there is a series-parallel graph G of girth 2 (3k -1)/2 -1 such that Ο‡ c (G) > 4k/(2k -1)