Paper Info
Title
Reducing hypergraph coloring to clique search
Abstract
It is known that the legal coloring of the nodes of a given graph can be reduced to a clique search problem. This paper generalizes this result for hypergraphs. Namely, we will show how legal coloring of the nodes of a hypergraph can be reduced to clique search in a uniform hypergraph. Replacing ordinary graphs by hypergraphs extends the descriptive power of graph models. In addition searching cliques in uniform hypergraphs may improve the efficiency of computations. As an illustration we will apply the reformulation technique to a hypergraph coloring problem due to Voloshin.
Year
DOI
Venue
2019
10.1016/j.dam.2018.09.010
Discrete Applied Mathematics
Keywords
Field
DocType
Coloring the nodes of a hypergraph,Independent set,Clique in a uniform hypergraph,Conflict graph,Combinatorial optimization
Discrete mathematics,Graph,Combinatorics,Clique,Hypergraph,Constraint graph,Search problem,Mathematics,Computation,Coloring problem
Journal
Volume
ISSN
Citations 
264
0166-218X
0
PageRank 
References 
Authors
0.34
4
2
Name
Order
Citations
PageRank
Sándor Szabó1105.11
Bogdan Zavalnij231.41