Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 14

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

Choice-Perfect Graphs

100%
Tuza Z.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
231-242
EN
Given a graph G = (V,E) and a set Lv of admissible colors for each vertex v ∈ V (termed the list at v), a list coloring of G is a (proper) vertex coloring ϕ : V → S v2V Lv such that ϕ(v) ∈ Lv for all v ∈ V and ϕ(u) 6= ϕ(v) for all uv ∈ E. If such a ϕ exists, G is said to be list colorable. The choice number of G is the smallest natural number k for which G is list colorable whenever each list contains at least k colors. In this note we initiate the study of graphs in which the choice number equals the clique number or the chromatic number in every induced subgraph. We call them choice-ω-perfect and choice-χ-perfect graphs, respectively. The main result of the paper states that the square of every cycle is choice-χ-perfect.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Graph colorings with local constraints - a survey

100%
Tuza Z.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 2
161-228
EN
We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered. In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers $c_v$ for the vertices v ∈ V are given, and the question is whether there can be chosen a subset C(v) ⊆ L(v) of cardinality $c_v$ for each vertex in such a way that the sets C(v),C(v') are disjoint for each pair v,v' of adjacent vertices. The particular case of constant |L(v)| with $c_v$ = 1 for all v ∈ V leads to the concept of choice number, a graph parameter showing unexpectedly different behavior compared to the chromatic number, despite these two invariants have nearly the same value for almost all graphs. To illustrate typical techniques, some of the proofs are sketched.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Highly connected counterexamples to a conjecture on α-domination

100%
Tuza Z.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 3
435-440
EN
An infinite class of counterexamples is given to a conjecture of Dahme et al. [1] concerning the minimum size of a dominating vertex set that contains at least a prescribed proportion of the neighbors of each vertex not belonging to the set.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Generalized colorings and avoidable orientations

64%
Szigeti J., Tuza Z.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
137-145
EN
Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed graphs.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Domination in partitioned graphs

64%
Tuza Z., Vestergaard P.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
199-210
EN
Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_i$ denote the least number of vertices needed in G to dominate $V_i$. We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value of (γ₁+γ₂)/|V(G)| is shown to grow with the order of (logδ)/(δ).
6
Content available remote

Decompositions of Plane Graphs Under Parity Constrains Given by Faces

64%
Czap J., Tuza Z.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
521-530
EN
An edge coloring of a plane graph G is facially proper if no two faceadjacent edges of G receive the same color. A facial (facially proper) parity edge coloring of a plane graph G is an (facially proper) edge coloring with the property that, for each color c and each face f of G, either an odd number of edges incident with f is colored with c, or color c does not occur on the edges of f. In this paper we deal with the following question: For which integers k does there exist a facial (facially proper) parity edge coloring of a plane graph G with exactly k colors?
7
Content available remote

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

64%
Bujtás C., Tuza Z.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
759-772
EN
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.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The cost chromatic number and hypergraph parameters

64%
Bacsó G., Tuza Z.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 3
369-376
EN
In a graph, by definition, the weight of a (proper) coloring with positive integers is the sum of the colors. The chromatic sum is the minimum weight, taken over all the proper colorings. The minimum number of colors in a coloring of minimum weight is the cost chromatic number or strength of the graph. We derive general upper bounds for the strength, in terms of a new parameter of representations by edge intersections of hypergraphs.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Graphs without induced P₅ and C₅

64%
Bacsó G., Tuza Z.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
503-507
EN
Zverovich [Discuss. Math. Graph Theory 23 (2003), 159-162.] has proved that the domination number and connected domination number are equal on all connected graphs without induced P₅ and C₅. Here we show (with an independent proof) that the following stronger result is also valid: Every P₅-free and C₅-free connected graph contains a minimum-size dominating set that induces a complete subgraph.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Remarks on the existence of uniquely partitionable planar graphs

52%
Borowiecki M., Mihók P., Tuza Z., Voigt M.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
159-166
EN
We consider the problem of the existence of uniquely partitionable planar graphs. We survey some recent results and we prove the nonexistence of uniquely (𝓓₁,𝓓₁)-partitionable planar graphs with respect to the property 𝓓₁ "to be a forest".
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Color-bounded hypergraphs, V: host graphs and subdivisions

52%
Bujtás C., Tuza Z., Voloshin V.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
223-238
EN
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.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Dominating bipartite subgraphs in graphs

52%
Bacsó G., Michalak D., Tuza Z.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
85-94
EN
A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Graph domination in distance two

52%
Bacsó G., Tálos A., Tuza Z.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
121-128
EN
Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class 𝓓 of graphs, Domₖ 𝓓 is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ 𝓓 which is also connected. In our notation, Dom𝓓 coincides with Dom₁𝓓. In this paper we prove that $Dom Dom 𝓓_u = Dom₂ 𝓓_u$ holds for $𝓓_u$ = {all connected graphs without induced $P_u$} (u ≥ 2). (In particular, 𝓓₂ = {K₁} and 𝓓₃ = {all complete graphs}.) Some negative examples are also given.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

3-consecutive c-colorings of graphs

45%
Bujtás C., Sampathkumar E., Tuza Z., Subramanya M., Dominic C.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 3
393-405
EN
A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number $(χ̅)_{3CC}(G)$ of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with $(χ̅)_{3CC}(G) ≥ k$ for k = 3 and k = 4.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.