Plurigraph coloring and scheduling problems (Q2628259)

Summary: We define a new type of vertex coloring which generalizes vertex coloring in graphs, hypergraphs, and simplicial complexes. This coloring also generalizes oriented coloring, acyclic coloring, and star coloring. There is an associated symmetric function in noncommuting variables for which we give a deletion-contraction formula. In the case of graphs this symmetric function in noncommuting variables agrees with the chromatic symmetric function in noncommuting variables of \textit{D. D. Gebhard} and \textit{B. E. Sagan} [J. Algebr. Comb. 13, No. 3, 227--255 (2001; Zbl 0979.05105)]. Our vertex coloring is a special case of the scheduling problems defined by \textit{F. Breuer} and \textit{C. J. Klivans} [J. Comb. Theory, Ser. A 139, 59--79 (2016; Zbl 1328.05190)]. We show how the deletion-contraction law can be applied to scheduling problems. Also, we show that the chromatic symmetric function determines the degree sequence of uniform hypertrees, but there exists pairs of~3-uniform hypertrees which are not isomorphic yet have the same chromatic symmetric function.