کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8902929 1632396 2018 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs
چکیده انگلیسی
In this paper, we continue our study of 2-colorings in hypergraphs (see, Henning and Yeo, 2013). A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. It is known (see Thomassen, 1992) that every 4-uniform 4-regular hypergraph is 2-colorable. Our main result in this paper is a strengthening of this result. For this purpose, we define a vertex in a hypergraph H to be a free vertex in H if we can 2-color V(H)∖{v} such that every hyperedge in H contains vertices of both colors (where v has no color). We prove that every 4-uniform 4-regular hypergraph has a free vertex. This proves a conjecture in Henning and Yeo (2015). Our proofs use a new result on not-all-equal 3-SAT which is also proved in this paper and is of interest in its own right.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 8, August 2018, Pages 2285-2292
نویسندگان
, ,