Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: feasible set

Sortuj według:

Ogranicz wyniki do:

K3-Worm Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum

100%

Bujtás C., Tuza Z.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 3

759-772

A K3-WORM coloring of a graph G is an assignment of colors to the vertices in such a way that the vertices of each K3-subgraph of G get precisely two colors. We study graphs G which admit at least one such coloring. We disprove a conjecture of Goddard et al. [Congr. Numer. 219 (2014) 161-173] by proving that for every integer k ≥ 3 there exists a K3-WORM-colorable graph in which the minimum number of colors is exactly k. There also exist K3-WORM colorable graphs which have a K3-WORM coloring with two colors and also with k colors but no coloring with any of 3, . . . , k − 1 colors. We also prove that it is NP-hard to determine the minimum number of colors, and NP-complete to decide k-colorability for every k ≥ 2 (and remains intractable even for graphs of maximum degree 9 if k = 3). On the other hand, we prove positive results for d-degenerate graphs with small d, also including planar graphs.

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Color-bounded hypergraphs, V: host graphs and subdivisions

63%

Bujtás C., Tuza Z., Voloshin V.

Discussiones Mathematicae Graph Theory

2011

tom 31

nr 2

223-238

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.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Bujtás C.

2 Tuza Z.

1 Voloshin V.

1 2016

1 2011

Wyniki wyszukiwania

K3-Worm Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum

Color-bounded hypergraphs, V: host graphs and subdivisions