We define a new type of vertex coloring which generalizes vertex coloring in graphs, hypergraphs, andsimplicial complexes. To this coloring there is an associated symmetric function in noncommuting variables for whichwe give a deletion-contraction formula. In the case of graphs our symmetric function in noncommuting variablesagrees with the chromatic symmetric function in noncommuting variables of Gebhard and Sagan. Our vertex coloringis a special case of the scheduling problems defined by Breuer and Klivans. We show how the deletion-contractionlaw can be applied to scheduling problems.
Discrete Mathematics & Theoretical Computer Science