Temat: Path Partition Conjecture

Skocz do pozycji: 1.

Tytuł:: The directed path partition conjecture
Autorzy:: Frick, Marietjie
van Aardt, Susan
Dlamini, Gcina
Dunbar, Jean
Oellermann, Ortrud
Tematy:: longest path
Path Partition Conjecture
vertex partition
digraph
prismatic colouring; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744375.pdf Link otwiera się w nowym oknie
Opis:: 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.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: On the Strong Path Partition Conjecture
Autorzy:: de Wet, Johan P.
Dunbar, Jean E.
Frick, Marietjie
Oellermann, Ortrud R.
Tematy:: Strong Path Partition Conjecture
longest path; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59896527.pdf Link otwiera się w nowym oknie
Opis:: The detour order of a graph $G$, denoted by $\tau (G)$, is the order of a longest path in $G$. If $a$ and $b$ are positive integers and the vertex set of $G$ can be partitioned into two subsets $A$ and $B$ such that $\tau(\langle A \rangle) \le a$ and $\tau(\langle B \rangle) \le b$, we say that $(A,B)$ is an $(a,b)$-partition of $G$. If equality holds in both instances, we call $(A,B)$ an exact $(a,b)$-partition. The Path Partition Conjecture (PPC) asserts that if $G$ is any graph and $a,b$ any pair of positive integers such that $\tau (G)=a+b$, then $G$ has an $(a,b)$-partition. The Strong PPC asserts that under the same circumstances $G$ has an exact $(a,b)$-partition. While a substantial body of work in support of the PPC has been developed over the past three decades, no results on the Strong PPC have yet appeared in the literature. In this paper we prove that the Strong PPC holds for $a\leq 8$.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: A Survey of the Path Partition Conjecture
Autorzy:: Frick, Marietjie
Tematy:: Path Partition Conjecture
Path Kernel Conjecture
generalized colourings
additive hereditary properties; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/30146727.pdf Link otwiera się w nowym oknie
Opis:: The Path Partition Conjecture (PPC) states that if G is any graph and (λ₁, λ₂) any pair of positive integers such that G has no path with more than λ₁ + λ₂ vertices, then there exists a partition (V₁, V₂) of the vertex set of G such that V_i 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.
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja