Equitable coloring of hypergraphs

Hanna Furmańczyk , Paweł Obszarski

Abstract

A hypergraph is equitably k-colorable if its vertices can be partitioned into k sets/color classes in such a way that monochromatic edges are avoided and the number of vertices in any two color classes differs by at most one. We prove that the problem of equitable 2-coloring of hypergraphs is NP-complete even for 3-uniform hyperstars. Finally, we apply the method of dynamic programming for designing a polynomial-time algorithm to equitably k-color linear hypertrees, where k≥2 is fixed.
Autor Hanna Furmańczyk (WMFiI / II)
Hanna Furmańczyk
- Instytut Informatyki
, Paweł Obszarski
Paweł Obszarski
-
Tytuł czasopisma/seriiDiscrete Applied Mathematics, ISSN 0166-218X, (N/A 70 pkt)
Rok wydania2019
Tom261
Paginacja186-192
Objętość publikacji w arkuszach wydawniczych0.5
Słowa kluczowe w języku angielskimequitable coloring, hypergraph, linear hypertree, feasible sequence
Klasyfikacja ASJC2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics
DOIDOI:10.1016/j.dam.2019.01.016
URL https://doi.org/10.1016/j.dam.2019.01.016
Języken angielski
Punktacja (całkowita)70
PunktacjaPunktacja MNiSW = 70.0, 30-09-2019, ArticleFromJournal
Wskaźniki publikacji Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.17; Impact Factor WoS: 2017 = 0.932 (2) - 2017=1.008 (5)
Liczba cytowań*
Cytuj
Udostępnij Udostępnij

Pobierz odnośnik do tego rekordu


* Podana liczba cytowań wynika z analizy informacji dostępnych w Internecie i jest zbliżona do wartości obliczanej przy pomocy systemu Publish or Perish.
Powrót