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: 10

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  graph coloring
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Generalized colorings and avoidable orientations

100%
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.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Frequency planning and ramifications of coloring

100%
Eisenblätter A., Grötschel M., Koster A.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
51-88
EN
This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical and organizational side constraints. Among these ramifications are T-coloring and list coloring. To model all the subtleties, the techniques of integer programming have proven to be very useful.The ability to produce good frequency plans in practice is essential for the quality of mobile phone networks. The present algorithmic solution methods employ variants of some of the traditional coloring heuristics as well as more sophisticated machinery from mathematical programming. This paper will also address this issue.Finally, this paper discusses several practical frequency assignment problems in detail, states the associated mathematical models, and also points to public electronic libraries of frequency assignment problems from practice. The associated graphs have up to several thousand vertices and range form rather sparse to almost complete.
3
Content available remote

Choice-Perfect Graphs

80%
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.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On-line 𝓟-coloring of graphs

80%
Borowiecki P.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 3
389-401
EN
For a given induced hereditary property 𝓟, a 𝓟-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property 𝓟. We consider the effectiveness of on-line 𝓟-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function of any stingy on-line 𝓟-coloring algorithm. In the class of generalized trees, we characterize graphs critical for the greedy 𝓟-coloring. A class of graphs for which a greedy algorithm always generates optimal 𝓟-colorings for the property 𝓟 = K₃-free is given.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph

80%
Mojdeh D.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 1
59-72
EN
In a given graph G = (V,E), a set of vertices S with an assignment of colors to them is said to be a defining set of the vertex coloring of G, if there exists a unique extension of the colors of S to a c ≥ χ(G) coloring of the vertices of G. A defining set with minimum cardinality is called a minimum defining set and its cardinality is the defining number, denoted by d(G,c). The d(G = Cₘ × Kₙ, χ(G)) has been studied. In this note we show that the exact value of defining number d(G = Cₘ × Kₙ, c) with c > χ(G), where n ≥ 2 and m ≥ 3, unless the defining number $d(K₃×C_{2r},4)$, which is given an upper and lower bounds for this defining number. Also some bounds of defining number are introduced.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The NP-completeness of automorphic colorings

80%
Mazzuoccolo G.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 4
705-710
EN
Given a graph G, an automorphic edge(vertex)-coloring of G is a proper edge(vertex)-coloring such that each automorphism of the graph preserves the coloring. The automorphic chromatic index (number) is the least integer k for which G admits an automorphic edge(vertex)-coloring with k colors. We show that it is NP-complete to determine the automorphic chromatic index and the automorphic chromatic number of an arbitrary graph.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The cost chromatic number and hypergraph parameters

80%
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.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Analogues of cliques for oriented coloring

80%
Klostermeyer W., MacGillivray G.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
373-387
EN
We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

3-consecutive c-colorings of graphs

80%
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.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Graph colorings with local constraints - a survey

61%
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.
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ć.