Plurigraph coloring and scheduling problems (Q2628259)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Plurigraph coloring and scheduling problems |
scientific article |
Statements
Plurigraph coloring and scheduling problems (English)
0 references
13 June 2017
0 references
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.
0 references
graph coloring
0 references
deletion-contraction
0 references
chromatic symmetric function
0 references
scheduling problem
0 references
plurigraph
0 references
0 references