کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419212 683753 2016 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Exploring the concept of perfection in 3-hypergraphs
ترجمه فارسی عنوان
بررسی مفهوم کمال در 3 ابرگراف
کلمات کلیدی
کمال در 3 ابرگراف؛ انتقال پذیری در 3 ابرگراف؛ مقایسه 3 ابرگراف
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 164–170
نویسندگان
, , ,