Plurigraph coloring and scheduling problems

MaRDI QIDQ2628259zbMATH OpenFDO

Authors John Machacek

Publication date 13 June 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.09469, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p29

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chromatic symmetric functiondeletion-contractiongraph coloringplurigraphscheduling problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Symmetric functions and generalizations (05E05) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Abstract: 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 Gebhard and Sagan. Our vertex coloring is a special case of the scheduling problems defined by Breuer and Klivans. 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 exist pairs on $3$-uniform hypertrees which are not isomorphic yet have the same chromatic symmetric function.

Review text

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.

Recommendations

• scientific article; zbMATH DE number 7203465
• Chromatic scheduling
• Scheduling Problems and Mixed Graph Colorings
• A chromatic symmetric function in noncommuting variables
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.

Cites work

• A chromatic symmetric function in noncommuting variables
• A symmetric function generalization of the chromatic polynomial of a graph
• Acyclic colorings of planar graphs
• Chromatic symmetric functions of hypertrees
• Colorings of plane graphs: a survey
• Combinatorial Hopf algebras of simplicial complexes.
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• Homomorphisms and colourings of oriented graphs: an updated survey
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 7203465 (Why is no real title available?)
• Hypergraphs and a functional equation of Bouwkamp and de Bruijn
• On chromaticity of hypergraphs
• On distinguishing trees by their chromatic symmetric functions
• Oriented graph coloring
• Practical graph isomorphism. II.
• Proper caterpillars are distinguished by their chromatic symmetric function
• Scheduling problems
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures

Cited in

(7)

• Extensions of coloring models for scheduling purposes
• New invariants for permutations, orders and graphs
• scientific article; zbMATH DE number 3435543 (Why is no real title available?)
• scientific article; zbMATH DE number 7203465 (Why is no real title available?)
• “Rent-or-Buy” Scheduling and Cost Coloring Problems
• List-graph colouring for multiple depot vehicle scheduling
• Scheduling problems

Describes a project that uses

Uses Software

• nauty
• Traces
• SageMath

This page was built for publication: Plurigraph coloring and scheduling problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2628259)