Mixed interval hypergraphs
type: Item
instance of: scholarly article
title: Mixed interval hypergraphs
zbMATH Open document ID: 0882.05100
DOI: 10.1016/S0166-218X(97)89209-8
author: Elena Bulgaru
author: V. I. Voloshin
published in: Discrete Applied Mathematics
publication date: 1997-08-28T00:00:00Z
full work available at URL: dam
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.
reviewed by: Andreas Brandstädt
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1053464
zbMATH Keywords: mixed hypergraph
zbMATH Keywords: coloring
zbMATH Keywords: chromatic number
zbMATH Keywords: linear time algorithms
MaRDI profile type: Publication
cites work: Q3993087
cites work: Q4732117
cites work: Q4842710
Recommended article: Q4732117
Recommended article: Mixed hypergraphs and beyond
Recommended article: Mixed unit interval bigraphs
Recommended article: Intersections of hypergraphs
Recommended article: Hypergraphs and intervals. II.
Recommended article: On intersecting hypergraphs
Recommended article: A Characterization of Mixed Unit Interval Graphs
Recommended article: Pseudo-chordal mixed hypergraphs
Recommended article: Mixed colorings of hypergraphs
description: scientific article; zbMATH DE number 1053464