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

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

Wyniki wyszukiwania

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

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

Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs

100%
Kubicka E., Kubicki G., McKeon K. A.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 3
541-555
EN
Given graphs G and H, a vertex coloring c : V (G) →ℕ is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ (H,G), is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G, ∑(H,G), is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for ∑(H,G), discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, Gk with the property that k more colors than χ (H,G) are required to realize ∑(H,G) for H-free colorings. More complexity results and constructions of graphs requiring extra colors are given for planar and outerplanar graphs.
2
Content available remote

A Different Short Proof of Brooks’ Theorem

100%
Rabern L.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
633-634
EN
Lovász gave a short proof of Brooks’ theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On acyclic colorings of direct products

100%
Špacapan S., Horvat A.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 2
323-333
EN
A coloring of a graph G is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees T₁ and T₂ equals min{Δ(T₁) + 1, Δ(T₂) + 1}. We also prove that the acyclic chromatic number of direct product of two complete graphs Kₘ and Kₙ is mn-m-2, where m ≥ n ≥ 4. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Upper bounds on the b-chromatic number and results for restricted graph classes

100%
Alkhateeb M., Kohl A.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 4
709-735
EN
A b-coloring of a graph G by k colors is a proper vertex coloring such that every color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k-1 color classes. The b-chromatic number $χ_b(G)$ is the maximum integer k for which G has a b-coloring by k colors. Moreover, the graph G is called b-continuous if G admits a b-coloring by k colors for all k satisfying $χ(G) ≤ k ≤ χ_b(G)$. In this paper, we establish four general upper bounds on $χ_b(G)$. We present results on the b-chromatic number and the b-continuity problem for special graphs, in particular for disconnected graphs and graphs with independence number 2. Moreover we determine $χ_b(G)$ for graphs G with minimum degree δ(G) ≥ |V(G)|-3, graphs G with clique number ω(G) ≥ |V(G)|-3, and graphs G with independence number α(G) ≥ |V(G)|-2. We also prove that these graphs are b-continuous.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The s-packing chromatic number of a graph

100%
Goddard W., Xu H.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 4
795-806
EN
Let S = (a₁, a₂, ...) be an infinite nondecreasing sequence of positive integers. An S-packing k-coloring of a graph G is a mapping from V(G) to {1,2,...,k} such that vertices with color i have pairwise distance greater than $a_i$, and the S-packing chromatic number $χ_S(G)$ of G is the smallest integer k such that G has an S-packing k-coloring. This concept generalizes the concept of proper coloring (when S = (1,1,1,...)) and broadcast coloring (when S = (1,2,3,4,...)). In this paper, we consider bounds on the parameter and its relationship with other parameters. We characterize the graphs with $χ_S = 2$ and determine $χ_S$ for several common families of graphs. We examine $χ_S$ for the infinite path and give some exact values and asymptotic bounds. Finally we consider complexity questions, especially about recognizing graphs with $χ_S = 3$.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Associative graph products and their independence, domination and coloring numbers

88%
Nowakowski R., Rall D.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 1
53-79
EN
Associative products are defined using a scheme of Imrich & Izbicki [18]. These include the Cartesian, categorical, strong and lexicographic products, as well as others. We examine which product ⊗ and parameter p pairs are multiplicative, that is, p(G⊗H) ≥ p(G)p(H) for all graphs G and H or p(G⊗H) ≤ p(G)p(H) for all graphs G and H. The parameters are related to independence, domination and irredundance. This includes Vizing's conjecture directly, and indirectly the Shannon capacity of a graph and Hedetniemi's coloring conjecture.
7
Content available remote

Vertex Colorings without Rainbow Subgraphs

88%
Goddard W., Xu H.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 4
989-1005
EN
Given a coloring of the vertices of a graph G, we say a subgraph is rainbow if its vertices receive distinct colors. For a graph F, we define the F-upper chromatic number of G as the maximum number of colors that can be used to color the vertices of G such that there is no rainbow copy of F. We present some results on this parameter for certain graph classes. The focus is on the case that F is a star or triangle. For example, we show that the K3-upper chromatic number of any maximal outerplanar graph on n vertices is [n/2] + 1.
8
Content available remote

Worm Colorings

88%
Goddard W., Wash K., Xu H.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 3
571-584
EN
Given a coloring of the vertices, we say subgraph H is monochromatic if every vertex of H is assigned the same color, and rainbow if no pair of vertices of H are assigned the same color. Given a graph G and a graph F, we define an F-WORM coloring of G as a coloring of the vertices of G without a rainbow or monochromatic subgraph H isomorphic to F. We present some results on this concept especially as regards to the existence, complexity, and optimization within certain graph classes. The focus is on the case that F is the path on three vertices.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Intersection graph of gamma sets in the total graph

75%
Chelvam T., Asir T.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 2
341-356
EN
In this paper, we consider the intersection graph $I_{Γ}(ℤₙ)$ of gamma sets in the total graph on ℤₙ. We characterize the values of n for which $I_{Γ}(ℤₙ)$ is complete, bipartite, cycle, chordal and planar. Further, we prove that $I_{Γ}(ℤₙ)$ is an Eulerian, Hamiltonian and as well as a pancyclic graph. Also we obtain the value of the independent number, the clique number, the chromatic number, the connectivity and some domination parameters of $I_{Γ}(ℤₙ)$.
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ć.