Chromatic Spectrum of K_s-WORM Colorings of K_n

摘要

An H-WORM coloring of a simple graph G is the coloring of the vertices of G such that no copy of H subset of G is monochrome or rainbow. In a recently published article by one of the authors [3], it was claimed that the number of r-partitions in a K-s-WORM coloring of K-n is zeta(r) = {n r}, where {n r} denotes the Stirling number of the second kind, for all 3 = r = s n. We found that zeta(r) = {n r} if and only if inverted right perpendicularn+3/2inverted left perpendicular s = n with r s. Further investigations into zeta(2), given any K-3-WORM coloring of K-n, show its relation with the number of spanning trees of cacti and the Catalan numbers. Moreover, we extend the notion of H-WORM colorings to (H-1; H-2)-mixed colorings, where H-1 and H-2 are distinct subgraphs of G; these coloring constraints are closely related to those of mixed hypergraph colorings.