Edge-coloring of 3-uniform hypergraphs

DOI10.1016/J.DAM.2016.06.009MaRDI QIDQ729801zbMATH OpenOpenAlexFDO

Authors Paweł Obszarski, Andrzej Jastrzȩbski

Publication date 22 December 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2016.06.009

zbMATH Keywords

3-uniform hypergraphedge coloringscheduling

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The complexity of vertex coloring problems in uniform hypergraphs with high degree
• scientific article; zbMATH DE number 1305101
• Approximation of 3-Edge-Coloring of Cubic Graphs
• Edge coloring complete uniform hypergraphs with many components
• Approximate coloring of uniform hypergraphs

Cites work

• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• An O(qn) algorithm to q-color a proper family of circular arcs
• Asymptotic behavior of the chromatic index for hypergraphs
• Graph Classes: A Survey
• scientific article; zbMATH DE number 25252 (Why is no real title available?)
• scientific article; zbMATH DE number 2122440 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• NP completeness of the edge precoloring extension problem on bipartite graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• The Complexity of Coloring Circular Arcs and Chords
• The NP-Completeness of Edge-Coloring

Cited in

(13)

• Concepts on coloring of cluster hypergraphs with application
• Complete colourings of hypergraphs
• Reducing hypergraph coloring to clique search
• A note on the least number of edges of 3-uniform hypergraphs with upper chromatic number 2
• The matroid intersection cover problem
• The complexity of vertex coloring problems in uniform hypergraphs with high degree
• On a 3-uniform hypergraph coloring problem in the integers
• The chromatic spectrum of 3-uniform bi-hypergraphs
• Edge intersection graphs of linear 3-uniform hypergraphs
• Three measures of edge-uncolorability
• Gap one bounds for the equitable chromatic number of block graphs
• 3-consecutive edge coloring of a graph
• Efficiently coloring the intersection of a general matroid and combinatorial matroids

This page was built for publication: Edge-coloring of 3-uniform hypergraphs

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