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

On the completeness of decomposable properties of graphs

80%
Hałuszczak M., Vateha P.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
229-236
EN
Let 𝓟₁,𝓟₂ be additive hereditary properties of graphs. A (𝓟₁,𝓟₂)-decomposition of a graph G is a partition of E(G) into sets E₁, E₂ such that induced subgraph $G[E_i]$ has the property $𝓟_i$, i = 1,2. Let us define a property 𝓟₁⊕𝓟₂ by {G: G has a (𝓟₁,𝓟₂)-decomposition}. A property D is said to be decomposable if there exists nontrivial additive hereditary properties 𝓟₁, 𝓟₂ such that D = 𝓟₁⊕𝓟₂. In this paper we determine the completeness of some decomposable properties and we characterize the decomposable properties of completeness 2.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Weakly P-saturated graphs

80%
Borowiecki M., Sidorowicz E.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
17-29
EN
For a hereditary property 𝓟 let $k_{𝓟}(G)$ denote the number of forbidden subgraphs contained in G. A graph G is said to be weakly 𝓟-saturated, if G has the property 𝓟 and there is a sequence of edges of G̅, say $e₁,e₂,...,e_l$, such that the chain of graphs $G = G₀ ⊂ G_0 + e₁ ⊂ G₁ + e₂ ⊂ ... ⊂ G_{l-1} + e_l = G_l = K_n(G_{i+1} = G_i + e_{i+1})$ has the following property: $k_{𝓟}(G_{i+1}) > k_{𝓟}(G_i)$, 0 ≤ i ≤ l-1. In this paper we shall investigate some properties of weakly saturated graphs. We will find upper bound for the minimum number of edges of weakly 𝓓ₖ-saturated graphs of order n. We shall determine the number wsat(n,𝓟) for some hereditary properties.
4
Content available remote

Hamiltonicity and Generalised Total Colourings of Planar Graphs

80%
Borowiecki M., Broere I.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
243-257
EN
The total generalised colourings considered in this paper are colourings of graphs such that the vertices and edges of the graph which receive the same colour induce subgraphs from two prescribed hereditary graph properties while incident elements receive different colours. The associated total chromatic number is the least number of colours with which this is possible. We study such colourings for sets of planar graphs and determine, in particular, upper bounds for these chromatic numbers for proper colourings of the vertices while the monochromatic edge sets are allowed to be forests. We also prove that if an even planar triangulation has a Hamilton cycle H for which there is no cycle among the edges inside H, then such a graph needs at most four colours for a total colouring as described above. The paper is concluded with some conjectures and open problems.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Hereditary domination and independence parameters

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

On partitions of hereditary properties of graphs

80%
Borowiecki M., Fiedorowicz A.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 3
377-387
EN
In this paper a concept 𝓠-Ramsey Class of graphs is introduced, where 𝓠 is a class of bipartite graphs. It is a generalization of well-known concept of Ramsey Class of graphs. Some 𝓠-Ramsey Classes of graphs are presented (Theorem 1 and 2). We proved that 𝓣₂, the class of all outerplanar graphs, is not 𝓓₁-Ramsey Class (Theorem 3). This results leads us to the concept of acyclic reducible bounds for a hereditary property 𝓟 . For 𝓣₂ we found two bounds (Theorem 4). An improvement, in some sense, of that in Theorem is given.
7
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.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A note on joins of additive hereditary graph properties

80%
Drgas-Burchardt E.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 3
413-418
EN
Let $L^a$ denote a set of additive hereditary graph properties. It is a known fact that a partially ordered set $(L^a, ⊆ )$ is a complete distributive lattice. We present results when a join of two additive hereditary graph properties in $(L^a, ⊆ )$ has a finite or infinite family of minimal forbidden subgraphs.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Maximal hypergraphs with respect to the bounded cost hereditary property

80%
Drgas-Burchardt E., Fiedorowicz A.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
67-77
EN
The hereditary property of hypergraphs generated by the cost colouring notion is considered in the paper. First, we characterize all maximal graphs with respect to this property. Second, we give the generating function for the sequence describing the number of such graphs with the numbered order. Finally, we construct a maximal hypergraph for each admissible number of vertices showing some density property. All results can be applied to the problem of information storage.
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ć.