Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419212 | Discrete Applied Mathematics | 2016 | 7 Pages |
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
Natalia García-Colín, Amanda Montejano, Deborah Oliveros,