Győri, Ervin and Kostochka, A. and McConvey, A. and Yager, D. (2016) A list version of graph packing. DISCRETE MATHEMATICS, 339 (8). pp. 2178-2185. ISSN 0012-365X
|
Text
1501.02488.pdf Download (390kB) | Preview |
Abstract
We consider the following generalization of graph packing. Let G1=V1,E1) and G2=(V2,E2) be graphs of order n and G3=(V1 ∪ V2, E3)a bipartite graph. A bijection f from V1 onto V2 is a list packing of the triple (G1, G2, G3) if uv ∈ E1 implies f(u)f(v) ∉ E2 and for all v ∈ V1 vf(v) ∉ E3. We extend the classical results of Sauer and Spencer and Bollobás and Eldridge on packing of graphs with small sizes or maximum degrees to the setting of list packing. In particular, we extend the well-known Bollobás-Eldridge Theorem, proving that if Δ(G1)≤n-2,Δ(G2)≤n-2,Δ(G3)≤n-1, and |E1|+|E2|+|E3|≤2n-3, then either (G1, G2, G3) packs or is one of 7 possible exceptions. © 2016 Elsevier B.V. All rights reserved.
| Item Type: | Article |
|---|---|
| Additional Information: | N1 Funding Details: 101536, OTKA, National Science Foundation N1 Funding Details: 15-01-05867, NSF, National Science Foundation N1 Funding Details: 16-01-00499, NSF, National Science Foundation N1 Funding Details: 78439, OTKA, National Science Foundation N1 Funding Details: DMS 08-38434, NSF, National Science Foundation N1 Funding Details: DMS-1266016, NSF, National Science Foundation N1 Funding Details: RFBR, National Science Foundation |
| Uncontrolled Keywords: | Maximum degree; list coloring; Graph packing; Edge sum |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 03 Jan 2017 09:09 |
| Last Modified: | 03 Jan 2017 09:09 |
| URI: | http://real.mtak.hu/id/eprint/44188 |
Actions (login required)
 |
Edit Item |
