Article ID Journal Published Year Pages File Type
419212 Discrete Applied Mathematics 2016 7 Pages PDF
Abstract

The natural extension of the concept of perfection in graphs to hypergraphs is to define a uniform mm-hypergraph, HH, as perfect  , if it satisfies that for every subhypergraph H′H′, χ(H′)=⌈ω(H′)m−1⌉, where χ(H′)χ(H′) and ω(H′)ω(H′) are the chromatic and clique number of H′H′, respectively.It is known that comparability graphs are perfect. In this paper we introduce the concept of comparability 3-hypergraphs (those that can be transitively oriented) with the aim of proving that these are not perfect according to the natural definition. More explicitly, we exhibit three different subfamilies of comparability 3-hypergraphs which show different behaviors in respect to the relationship between the chromatic number and the clique number.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,