Search
Didn't find any results in this catalog!
But we have some results in other catalogs.Search results for: HYPERGRAPH COLORING
-
Equitable coloring of hypergraphs
PublicationA hypergraph is equitablyk-colorable if its vertices can be partitioned into k sets/colorclasses in such a way that monochromatic edges are avoided and the number of verticesin 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...
-
Edge-coloring of 3-uniform hypergraphs
PublicationWe consider edge-colorings of 3-uniform hypergraphs which is a natural generalization of the problem of edge-colorings of graphs. Various classes of hypergraphs are discussed and we make some initial steps to establish the border between polynomial and NP-complete cases. Unfortunately, the problem appears to be computationally difficult even for relatively simple classes of hypergraphs.
-
Weighted 2-sections and hypergraph reconstruction
PublicationIn the paper we introduce the notion of weighted 2-sections of hypergraphs with integer weights and study the following hypergraph reconstruction problems: (1) Given a weighted graph , is there a hypergraph H such that is its weighted 2-section? (2) Given a weighted 2-section , find a hypergraph H such that is its weighted 2-section. We show that (1) is NP-hard even if G is a complete graph or integer weights w does not exceed...
-
Independence in uniform linear triangle-free hypergraphs
PublicationThe independence number a(H) of a hypergraph H is the maximum cardinality of a set of vertices of H that does not contain an edge of H. Generalizing Shearer’s classical lower bound on the independence number of triangle-free graphs Shearer (1991), and considerably improving recent results of Li and Zang (2006) and Chishti et al. (2014), we show a new lower bound for a(H) for an r-uniform linear triangle-free hypergraph H with r>=2.
-
On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublicationIn the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.
-
Dynamic coloring of graphs
PublicationDynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In...
-
Harmonions Coloring of Graphs.
PublicationProblem kolorowania grafów jest motywowany radionawigacją lotniczą, kompresją obrazów i in. W rozdziale podano podstawowe fakty dotyczące tego modelu kolorowania, a wsród nich dolne i górne oszacowania na liczbę harmoniczną i algorytm o złożoności 0 (mm3) dający bardzo dobre pokolorowania przybliżone.
-
Classical coloring of graphs.
PublicationRozdział obejmuje klasyczne kolorowanie krawędzi i wierzołków w grafach prostych. Oprócz podstawowych definicji podane zostały najczęściej stosowane metody przybliżone oraz ich właściwości. Dodatkowo rozdział zawiera przegląd znanych benczmarków dla podanych metod w kontekście klasycznego modelu kolorowania.
-
Sum Coloring of Graphs.
PublicationRozdział jest poświęcony sumacyjnemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Rank Coloring of Graphs.
PublicationRozdział jest poświęcony uporządkowanemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.