Packing \(d\)-degenerate graphs (Q2464154)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5219089
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Packing \(d\)-degenerate graphs |
scientific article; zbMATH DE number 5219089 |
Statements
Packing \(d\)-degenerate graphs (English)
0 references
10 December 2007
0 references
The Bollobás-Eldridge-Catlin conjecture asserts that two \(n\)-vertex graphs of maximum degree \(\Delta_1\) and \(\Delta_2\) pack if \((\Delta_1+1)(\Delta_2+1) \leq n+1\). Under the additional hypothesis that the first graph is \(d\)-degenerate (i.e. every subgraph has a vertex of degree at most \(d\)), this paper establishes that when \(n > \max \{ 40\Delta_1\ln \Delta_2, 40 d \Delta_2 \}\), the two graphs pack. This is stronger than the stated conjecture when \(d\) is small. The extension to packing many \(d\)-degenerate graphs is also examined.
0 references
graph packing
0 references
\(d\)-degenerate graph
0 references
maximum degree
0 references
0.9147075414657592
0 references
0.8838544487953186
0 references
0.8817671537399292
0 references
0.8693540692329407
0 references
0.8693540692329407
0 references
