Minimum rainbow H-decompositions of graphs

Lale Özkahya; Yury Person

doi:10.1016/j.ejc.2018.03.002

Minimum rainbow H-decompositions of graphs

Lale Özkahya
, Yury Person

Division of Computer Software

Goethe University Frankfurt

Research output: Contribution to journal › Article › peer-review

Abstract

Given graphs G and H, we consider the problem of decomposing a properly edge-colored graph G into few parts consisting of rainbow copies of H and single edges. We establish a close relation to the previously studied problem of minimum H-decompositions, where an edge coloring does not matter and one is merely interested in decomposing graphs into copies of H and single edges.

Original language	English
Pages (from-to)	111-124
Number of pages	14
Journal	European Journal of Combinatorics
Volume	71
DOIs	https://doi.org/10.1016/j.ejc.2018.03.002
Publication status	Published - Jun 2018

Access to Document

10.1016/j.ejc.2018.03.002

Cite this

@article{ed08c82a71e9402ca580eee8a5af900f,

title = "Minimum rainbow H-decompositions of graphs",

abstract = "Given graphs G and H, we consider the problem of decomposing a properly edge-colored graph G into few parts consisting of rainbow copies of H and single edges. We establish a close relation to the previously studied problem of minimum H-decompositions, where an edge coloring does not matter and one is merely interested in decomposing graphs into copies of H and single edges.",

author = "Lale {\"O}zkahya and Yury Person",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier Ltd",

year = "2018",

month = jun,

doi = "10.1016/j.ejc.2018.03.002",

language = "English",

volume = "71",

pages = "111--124",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - Minimum rainbow H-decompositions of graphs

AU - Özkahya, Lale

AU - Person, Yury

PY - 2018/6

Y1 - 2018/6

N2 - Given graphs G and H, we consider the problem of decomposing a properly edge-colored graph G into few parts consisting of rainbow copies of H and single edges. We establish a close relation to the previously studied problem of minimum H-decompositions, where an edge coloring does not matter and one is merely interested in decomposing graphs into copies of H and single edges.

AB - Given graphs G and H, we consider the problem of decomposing a properly edge-colored graph G into few parts consisting of rainbow copies of H and single edges. We establish a close relation to the previously studied problem of minimum H-decompositions, where an edge coloring does not matter and one is merely interested in decomposing graphs into copies of H and single edges.

UR - https://www.scopus.com/pages/publications/85044119466

U2 - 10.1016/j.ejc.2018.03.002

DO - 10.1016/j.ejc.2018.03.002

M3 - Article

AN - SCOPUS:85044119466

SN - 0195-6698

VL - 71

SP - 111

EP - 124

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

Minimum rainbow H-decompositions of graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this