REAL

Reducing hypergraph coloring to clique search

Szabó, Sándor and Zavalnij, Bogdan (2019) Reducing hypergraph coloring to clique search. DISCRETE APPLIED MATHEMATICS, 264. pp. 196-207. ISSN 0166-218X

[img]
Preview
Text
1-s2.0-S0166218X1830475X-main.pdf
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (547kB) | Preview

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.

Item Type: Article
Uncontrolled Keywords: Coloring the nodes of a hypergraph; Independent set; Clique in a uniform hypergraph; Conflict graph; Combinatorial optimization
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 09 Oct 2019 07:26
Last Modified: 09 Oct 2019 07:26
URI: http://real.mtak.hu/id/eprint/102150

Actions (login required)

Edit Item Edit Item