Premium
Graphs with unique Ramsey colorings
Author(s) -
Grossman Jerrold W.
Publication year - 1983
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.3190070111
Subject(s) - combinatorics , mathematics , graph , factorization , discrete mathematics , algorithm
A pair of graphs ( H 1 , H 2 ) is a cleaver if there is a graph G with a unique factorization G = G 2 ⊕ G 2 such that G i does not contain a copy of H i . (In case H 1 = H 2 , H 1 is a cleaver if the factorization is unique up to interchange of factors.) A variety of positive and negative results on the existence of cleavers is obtained. For example (tree, complete graph) is a cleaver, and the triangle is the cleaver of an infinite collection of minimal graphs. On the other hand, stars are not cleavers.