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