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

help Sortuj według:

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

A Survey of the Path Partition Conjecture

100%
Frick M.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
117-131
EN
The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition (V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Detour chromatic numbers

64%
Frick M., Bullock F.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
283-291
EN
The nth detour chromatic number, χₙ(G) of a graph G is the minimum number of colours required to colour the vertices of G such that no path with more than n vertices is monocoloured. The number of vertices in a longest path of G is denoted by τ( G). We conjecture that χₙ(G) ≤ ⎡(τ(G))/n⎤ for every graph G and every n ≥ 1 and we prove results that support the conjecture. We also present some sufficient conditions for a graph to have nth chromatic number at most 2.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A path(ological) partition problem

51%
Broere I., Dorfling M., Dunbar J., Frick M.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 1
113-125
EN
Let τ(G) denote the number of vertices in a longest path of the graph G and let k₁ and k₂ be positive integers such that τ(G) = k₁ + k₂. The question at hand is whether the vertex set V(G) can be partitioned into two subsets V₁ and V₂ such that τ(G[V₁] ) ≤ k₁ and τ(G[V₂] ) ≤ k₂. We show that several classes of graphs have this partition property.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The order of uniquely partitionable graphs

51%
Broere I., Frick M., Mihók P.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
115-125
EN
Let 𝓟₁,...,𝓟ₙ be properties of graphs. A (𝓟₁,...,𝓟ₙ)-partition of a graph G is a partition {V₁,...,Vₙ} of V(G) such that, for each i = 1,...,n, the subgraph of G induced by $V_i$ has property $𝓟_i$. If a graph G has a unique (𝓟₁,...,𝓟ₙ)-partition we say it is uniquely (𝓟₁,...,𝓟ₙ)-partitionable. We establish best lower bounds for the order of uniquely (𝓟₁,...,𝓟ₙ)-partitionable graphs, for various choices of 𝓟₁,...,𝓟ₙ.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Maximal graphs with respect to hereditary properties

51%
Broere I., Frick M., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
51-66
EN
A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by V_i has property $P_i$; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. If P is a hereditary property, then a graph G is called P- maximal if G has property P but G+e does not have property P for every e ∈ E([G̅]). We present some general results on maximal graphs and also investigate P-maximal graphs for various specific choices of P, including reducible hereditary properties.
6
Content available remote

Independent Detour Transversals in 3-Deficient Digraphs

51%
van Aardt S., Frick M., Singleton J.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
261-275
EN
In 1982 Laborde, Payan and Xuong [Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983)] conjectured that every digraph has an independent detour transversal (IDT), i.e. an independent set which intersects every longest path. Havet [Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173] showed that the conjecture holds for digraphs with independence number two. A digraph is p-deficient if its order is exactly p more than the order of its longest paths. It follows easily from Havet’s result that for p = 1, 2 every p-deficient digraph has an independent detour transversal. This paper explores the existence of independent detour transversals in 3-deficient digraphs.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Uniquely partitionable graphs

51%
Bucko J., Frick M., Mihók P., Vasky R.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
103-113
EN
Let 𝓟₁,...,𝓟ₙ be properties of graphs. A (𝓟₁,...,𝓟ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph $G[V_i]$ induced by $V_i$ has property $𝓟_i$; i = 1,...,n. A graph G is said to be uniquely (𝓟₁, ...,𝓟ₙ)-partitionable if G has exactly one (𝓟₁,...,𝓟ₙ)-partition. A property 𝓟 is called hereditary if every subgraph of every graph with property 𝓟 also has property 𝓟. If every graph that is a disjoint union of two graphs that have property 𝓟 also has property 𝓟, then we say that 𝓟 is additive. A property 𝓟 is called degenerate if there exists a bipartite graph that does not have property 𝓟. In this paper, we prove that if 𝓟₁,..., 𝓟ₙ are degenerate, additive, hereditary properties of graphs, then there exists a uniquely (𝓟₁,...,𝓟ₙ)-partitionable graph.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A survey of hereditary properties of graphs

45%
Borowiecki M., Broere I., Frick M., Mihók P., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
5-50
EN
In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The directed path partition conjecture

45%
Frick M., van Aardt S., Dlamini G., Dunbar J., Oellermann O.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 3
331-343
EN
The Directed Path Partition Conjecture is the following: If D is a digraph that contains no path with more than λ vertices then, for every pair (a,b) of positive integers with λ = a+b, there exists a vertex partition (A,B) of D such that no path in D⟨A⟩ has more than a vertices and no path in D⟨B⟩ has more than b vertices. We develop methods for finding the desired partitions for various classes of digraphs.
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ć.