Temat: mixed hypergraph - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: Chromatic polynomials of mixed hypercycles
Autorzy:: Allagan, Julian A.
Slutzky, David
Tematy:: hypercycle
mixed hypergraph
chromatic polynomial; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/30148312.pdf Link otwiera się w nowym oknie
Opis:: We color the vertices of each of the edges of a C-hypergraph (or cohypergraph) in such a way that at least two vertices receive the same color and in every proper coloring of a $\mathcal{B}$-hypergraph (or bihypergraph), we forbid the cases when the vertices of any of its edges are colored with the same color (monochromatic) or when they are all colored with distinct colors (rainbow). In this paper, we determined explicit formulae for the chromatic polynomials of $\mathcal{C}$-hypercycles and $\mathcal{B}$-hypercycles.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: More Results on The Smallest One-Realization of A Given Set II
Autorzy:: Diao, Kefeng
Lu, Fuliang
Zhao, Ping
Tematy:: mixed hypergraph
feasible set
chromatic spectrum
gap
onerealization; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31343431.pdf Link otwiera się w nowym oknie
Opis:: Let S be a finite set of positive integers. A mixed hypergraph ℋ is a onerealization of S if its feasible set is S and each entry of its chromatic spectrum is either 0 or 1. The minimum number of vertices, denoted by δ₃(S), in a 3-uniform bi-hypergraph which is a one-realization of S was determined in [P. Zhao, K. Diao and F. Lu, More result on the smallest one-realization of a given set, Graphs Combin. 32 (2016) 835–850]. In this paper, we consider the minimum number of edges in a 3-uniform bi-hypergraph which already has the minimum number of vertices with respect of being a minimum bihypergraph that is one-realization of S. A tight lower bound on the number of edges in a 3-uniform bi-hypergraph which is a one-realization of S with δ₃(S) vertices is given.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges
Autorzy:: Axenovich, Maria
Karrer, Annette
Tematy:: hypergraph
chromatic number
mixed hypergraph
bihyper-graphs
monochromatic
rainbow
girth
selective; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32361723.pdf Link otwiera się w nowym oknie
Opis:: A classical result of Erdős and Hajnal claims that for any integers k, r, g ≥ 2 there is an r-uniform hypergraph of girth at least g with chromatic number at least k. This implies that there are sparse hypergraphs such that in any coloring of their vertices with at most k − 1 colors there is a monochromatic hyperedge. When there is no restriction on the number of the colors used, one can easily avoid monochromatic hyperedges. Then, however, so-called rainbow or multicolored hyperedges might appear. Nešetřil and Rödl [19] called hypergraphs such that in any vertex-coloring there is either a monochromatic or a rainbow hyperedge, selective. They showed an existence of selective r-uniform hypergraphs of girth g for any integers r, g ≥ 2 using probabilistic and explicit constructions. In this paper, we provide a slightly di erent construction of such hypergraphs and summarize the probabilistic approaches. The main building block of the construction, a part-rainbow-forced hypergraph, is of independent interest. This is an r-uniform r-partite hypergraph with a given girth such that in any vertex-coloring that is rainbow on each part, there is a rainbow hyperedge. We give a simple construction of such a hypergraph that does not use iterative amalgamation.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Color-bounded hypergraphs, V: host graphs and subdivisions
Autorzy:: Bujtás, Csilla
Tuza, Zsolt
Voloshin, Vitaly
Tematy:: mixed hypergraph
color-bounded hypergraph
vertex coloring
arboreal hypergraph
hypertree
feasible set
host graph
edge subdivision; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743863.pdf Link otwiera się w nowym oknie
Opis:: A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = {E₁,...,Eₘ}, together with integers $s_i$ and $t_i$ satisfying $1 ≤ s_i ≤ t_i ≤ |E_i|$ for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge $E_i$ satisfies $s_i ≤ |φ(E_i)| ≤ t_i$. The hypergraph ℋ is colorable if it admits at least one proper coloring.
We consider hypergraphs ℋ over a "host graph", that means a graph G on the same vertex set X as ℋ, such that each $E_i$ induces a connected subgraph in G. In the current setting we fix a graph or multigraph G₀, and assume that the host graph G is obtained by some sequence of edge subdivisions, starting from G₀.
The colorability problem is known to be NP-complete in general, and also when restricted to 3-uniform "mixed hypergraphs", i.e., color-bounded hypergraphs in which $|E_i| = 3$ and $1 ≤ s_i ≤ 2 ≤ t_i ≤ 3$ holds for all i ≤ m. We prove that for every fixed graph G₀ and natural number r, colorability is decidable in polynomial time over the class of r-uniform hypergraphs (and more generally of hypergraphs with $|E_i| ≤ r$ for all 1 ≤ i ≤ m) having a host graph G obtained from G₀ by edge subdivisions. Stronger bounds are derived for hypergraphs for which G₀ is a tree.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "mixed hypergraph" wg kryterium: Temat