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,50
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
Żródło punktacjijournalList
PunktacjaPunktacja MNiSW = 70.0, 26-02-2020, ArticleFromJournal
Wskaźniki publikacji Cytowania WoS = 0,000; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1,263; Impact Factor WoS: 2018 = 0,983 (2) - 2018=1,029 (5)
Liczba cytowań*1 (2020-07-06)
Cytuj
przetwarzanie
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
Potwierdzenie
Czy jesteś pewien?