Color-bounded hypergraphs. VI: Structural and functional jumps in complexity

DOI10.1016/j.disc.2012.09.020zbMath1277.05059OpenAlexW2076597551WikidataQ59072528 ScholiaQ59072528MaRDI QIDQ383764

Zsolt Tuza, Csilla Bujtás

Publication date: 6 December 2013

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

Full work available at URL: https://doi.org/10.1016/j.disc.2012.09.020

zbMATH Keywords

algorithmic complexitychromatic numbermixed hypergraphfeasible setupper chromatic numberhypergraph coloringcolor-bounded hypergraphinterval hypergraphstably bounded hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

On perfection and imperfection of one-realizations of a given set ⋮ Problems on cycles and colorings ⋮ On the structure of uniform one-realizations of a given set ⋮ More results on the smallest one-realization of a given set. II ⋮ Constrained colouring and \(\sigma\)-hypergraphs ⋮ Mixed hypergraphs and beyond

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Color-bounded hypergraphs, IV: Stable colorings of hypertrees
• Color-bounded hypergraphs. I: General results
• Color-bounded hypergraphs. II: Interval hypergraphs and hypertrees
• Trivially perfect graphs
• Mixed interval hypergraphs
• Tight approximations for resource constrained scheduling and bin packing
• Coloring mixed hypergraphs: theory, algorithms and applications
• Uncolorable mixed hypergraphs
• Color-bounded hypergraphs, V: host graphs and subdivisions
• A generalization of edge-coloring in graphs
• The Comparability Graph of a Tree
• Edge-Coloring and f-Coloring for Various Classes of Graphs
• Graph Classes: A Survey
• SCHEDULING FILE TRANSFERS UNDER PORT AND CHANNEL CONSTRAINTS
• A Note on "The Comparability Graph of a Tree"
• Chromatic polynomials of hypergraphs

This page was built for publication: Color-bounded hypergraphs. VI: Structural and functional jumps in complexity