Mixed interval hypergraphs

DOI10.1016/S0166-218X(97)89209-8MaRDI QIDQ1364778zbMATH OpenFDO

Authors Elena Bulgaru, V. I. Voloshin

Publication date 28 August 1997

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

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

chromatic numbercoloringlinear time algorithmsmixed hypergraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Review text

A mixed hypergraph \(H\) is a generalization of a hypergraph having two families of vertex subsets: edges and co-edges. A coloring of \(H\) is an assignment of vertices to colors such that in every edge at least two vertices have different colors and in every co-edge at least two vertices have the same color. The upper (lower) chromatic number is the maximum (minimum) number of colors in any coloring using all the colors. A mixed hypergraph \(H\) is a mixed interval hypergraph if there is a linear ordering of the vertex set such that every edge and every co-edge of \(H\) represent an interval of the vertex ordering. The authors study the lower and upper chromatic number of mixed interval hypergraphs and give linear time algorithms for finding them. Furthermore, they introduce and study the co-stability number and co-perfectness of such hypergraphs and characterize co-perfect mixed interval hypergraphs in terms of certain forbidden subhypergraphs called co-monostars and covered co-bistars.

Recommendations

• scientific article; zbMATH DE number 4117862
• Mixed hypergraphs and beyond
• Mixed unit interval bigraphs
• Intersections of hypergraphs
• Hypergraphs and intervals. II.
• On intersecting hypergraphs
• Pseudo-chordal mixed hypergraphs
• Mixed colorings of hypergraphs

Cited in

(22)

• Color-bounded hypergraphs. II: Interval hypergraphs and hypertrees
• Integer programming models for colorings of mixed hypergraphs
• Coloring mixed hypergraphs: theory, algorithms and applications
• More results on the smallest one-realization of a given set. II
• Uncolorable mixed hypergraphs
• The smallest uniform color-bounded hypergraphs which are one-realizations of a given set
• A note on the least number of edges of 3-uniform hypergraphs with upper chromatic number 2
• Coloring mixed hypertrees
• Circular mixed hypergraphs. II: The upper chromatic number
• Mixed unit interval bigraphs
• Circular and uniquely colorable mixed hypergraphs
• On perfection and imperfection of one-realizations of a given set
• C-perfect hypergraphs
• About perfection of circular mixed hypergraphs
• On the Upper Chromatic Numbers of Mixed Interval Hypertrees
• Color-bounded hypergraphs. VI: Structural and functional jumps in complexity
• Maximum number of colors: C-coloring and related problems
• scientific article; zbMATH DE number 1491631 (Why is no real title available?)
• scientific article; zbMATH DE number 1369938 (Why is no real title available?)
• Mixed hypergraphs and beyond
• Bounds on coloring trees without rainbow paths
• Mixed hypergraphs and other coloring problems

This page was built for publication: Mixed interval hypergraphs

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