Packing \(d\)-degenerate graphs (Q2464154): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jctb.2007.05.002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2161551214 / rank | |||
Normal rank |
Revision as of 00:02, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Packing \(d\)-degenerate graphs |
scientific article |
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