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

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

Vertex Colorings without Rainbow Subgraphs

100%
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.
2
Content available remote

Coloring subgraphs with restricted amounts of hues

100%
Goddard W., Melville R.
Open Mathematics
|
2017
|
tom 15
|
nr 1
1171-1180
EN
We consider vertex colorings where the number of colors given to specified subgraphs is restricted. In particular, given some fixed graph F and some fixed set A of positive integers, we consider (not necessarily proper) colorings of the vertices of a graph G such that, for every copy of F in G, the number of colors it receives is in A. This generalizes proper colorings, defective coloring, and no-rainbow coloring, inter alia. In this paper we focus on the case that A is a singleton set. In particular, we investigate the colorings where the graph F is a star or is 1-regular.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Orientation distance graphs revisited

100%
Goddard W., Kanakadandi K.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 1
125-136
EN
The orientation distance graph 𝓓ₒ(G) of a graph G is defined as the graph whose vertex set is the pair-wise non-isomorphic orientations of G, and two orientations are adjacent iff the reversal of one edge in one orientation produces the other. Orientation distance graphs was introduced by Chartrand et al. in 2001. We provide new results about orientation distance graphs and simpler proofs to existing results, especially with regards to the bipartiteness of orientation distance graphs and the representation of orientation distance graphs using hypercubes. We provide results concerning the orientation distance graphs of paths, cycles and other common graphs.
4
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$.
5
Content available remote

Worm Colorings

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

Hereditary domination and independence parameters

81%
Goddard W., Haynes T., Knisley D.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
239-248
EN
For a graphical property P and a graph G, we say that a subset S of the vertices of G is a P-set if the subgraph induced by S has the property P. Then the P-domination number of G is the minimum cardinality of a dominating P-set and the P-independence number the maximum cardinality of a P-set. We show that several properties of domination, independent domination and acyclic domination hold for arbitrary properties P that are closed under disjoint unions and subgraphs.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Offensive alliances in graphs

52%
Favaron O., Fricke G., Goddard W., Hedetniemi S., Hedetniemi S., Kristiansen P., Laskar R., Skaggs R.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
263-275
EN
A set S is an offensive alliance if for every vertex v in its boundary N(S)- S it holds that the majority of vertices in v's closed neighbourhood are in S. The offensive alliance number is the minimum cardinality of an offensive alliance. In this paper we explore the bounds on the offensive alliance and the strong offensive alliance numbers (where a strict majority is required). In particular, we show that the offensive alliance number is at most 2/3 the order and the strong offensive alliance number is at most 5/6 the order.
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ć.