Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs

Michael A. Henning; Anders Yeo

doi:10.1016/j.disc.2018.05.002

Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs

Michael A. Henning^*
, Anders Yeo

^*Kontaktforfatter

Institut for Matematik og Datalogi

University of Johannesburg

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

Abstract

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.

Originalsprog	Engelsk
Tidsskrift	Discrete Mathematics
Vol/bind	341
Udgave nummer	8
Sider (fra-til)	2285-2292
ISSN	0012-365X
DOI	https://doi.org/10.1016/j.disc.2018.05.002
Status	Udgivet - 2018

Finansiering

The authors express their sincere thanks to the anonymous referees for their meticulous and thorough reading of the paper. Their helpful comments enhanced the readability and exposition of the paper. The first author’s research was supported in part by the South African National Research Foundation and the University of Johannesburg .

Dokumenter og links

10.1016/j.disc.2018.05.002

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

Citationsformater

@article{732e651843844632b78b6f142cb474a6,

title = "Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs",

abstract = "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.",

keywords = "2-colorable, Bipartite, Free vertex, Hypergraphs, NAE-3-SAT, Transversal",

author = "Henning, \{Michael A.\} and Anders Yeo",

year = "2018",

doi = "10.1016/j.disc.2018.05.002",

language = "English",

volume = "341",

pages = "2285--2292",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "8",

}

TY - JOUR

T1 - Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs

AU - Henning, Michael A.

AU - Yeo, Anders

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - 2-colorable

KW - Bipartite

KW - Free vertex

KW - Hypergraphs

KW - NAE-3-SAT

KW - Transversal

U2 - 10.1016/j.disc.2018.05.002

DO - 10.1016/j.disc.2018.05.002

M3 - Journal article

AN - SCOPUS:85047598868

SN - 0012-365X

VL - 341

SP - 2285

EP - 2292

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 8

ER -

Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs

Abstract

Finansiering

Dokumenter og links

SDU link

Fingeraftryk

Citationsformater