Premium
Monochromatic Clique Decompositions of Graphs
Author(s) -
Liu Henry,
Pikhurko Oleg,
Sousa Teresa
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21851
Subject(s) - monochromatic color , combinatorics , mathematics , split graph , clique , discrete mathematics , partition (number theory) , clique graph , graph , block graph , 1 planar graph , chordal graph , line graph , graph power , physics , optics
Abstract Let G be a graph whose edges are colored with k colors, and H = ( H 1 , ⋯ , H k ) be a k ‐tuple of graphs. A monochromatic H ‐ decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a monochromatic copy of H i in color i , for some 1 ≤ i ≤ k . Letφ k ( n , H )be the smallest number ϕ, such that, for every order‐ n graph and every k ‐edge‐coloring, there is a monochromatic H ‐decomposition with at most ϕ elements. Extending the previous results of Liu and Sousa [Monochromatic K r ‐decompositions of graphs, J Graph Theory 76 (2014), 89–100], we solve this problem when each graph in H is a clique and n ≥ n 0 ( H )is sufficiently large.