Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "planar graphs" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 17
Tytuł:
A characterization of planar median graphs
Autorzy:
Peterin, Iztok
Powiązania:
https://bibliotekanauki.pl/articles/744189.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
median graphs
planar graphs
expansion
Opis:
Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 41-48
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Short cycles of low weight in normal plane maps with minimum degree 5
Autorzy:
Borodin, Oleg
Woodall, Douglas
Powiązania:
https://bibliotekanauki.pl/articles/744215.pdf
Data publikacji:
1998
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graphs
plane triangulation
Opis:
In this note, precise upper bounds are determined for the minimum degree-sum of the vertices of a 4-cycle and a 5-cycle in a plane triangulation with minimum degree 5: w(C₄) ≤ 25 and w(C₅) ≤ 30. These hold because a normal plane map with minimum degree 5 must contain a 4-star with $w(K_{1,4}) ≤ 30$. These results answer a question posed by Kotzig in 1979 and recent questions of Jendrol' and Madaras.
Źródło:
Discussiones Mathematicae Graph Theory; 1998, 18, 2; 159-164
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on Hamiltonian cycles in generalized Halin graphs
Autorzy:
Bojarska, Magdalena
Powiązania:
https://bibliotekanauki.pl/articles/744110.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graphs
Halin graphs
hamiltonian cycles
Opis:
We show that every 2-connected (2)-Halin graph is Hamiltonian.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 4; 701-704
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Uniquely partitionable planar graphs with respect to properties having a forbidden tree
Autorzy:
Bucko, Jozef
Ivančo, Jaroslav
Powiązania:
https://bibliotekanauki.pl/articles/744245.pdf
Data publikacji:
1999
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
uniquely partitionable planar graphs
forbidden graphs
Opis:
Let ₁, ₂ be graph properties. A vertex (₁,₂)-partition of a graph G is a partition {V₁,V₂} of V(G) such that for i = 1,2 the induced subgraph $G[V_i]$ has the property $_i$. A property ℜ = ₁∘₂ is defined to be the set of all graphs having a vertex (₁,₂)-partition. A graph G ∈ ₁∘₂ is said to be uniquely (₁,₂)-partitionable if G has exactly one vertex (₁,₂)-partition. In this note, we show the existence of uniquely partitionable planar graphs with respect to hereditary additive properties having a forbidden tree.
Źródło:
Discussiones Mathematicae Graph Theory; 1999, 19, 1; 71-78
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Partitions of some planar graphs into two linear forests
Autorzy:
Borowiecki, Piotr
Hałuszczak, Mariusz
Powiązania:
https://bibliotekanauki.pl/articles/972026.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
linear forest
bipartition
planar graphs
Opis:
A linear forest is a forest in which every component is a path. It is known that the set of vertices V(G) of any outerplanar graph G can be partitioned into two disjoint subsets V₁,V₂ such that induced subgraphs ⟨V₁⟩ and ⟨V₂⟩ are linear forests (we say G has an (LF, LF)-partition). In this paper, we present an extension of the above result to the class of planar graphs with a given number of internal vertices (i.e., vertices that do not belong to the external face at a certain fixed embedding of the graph G in the plane). We prove that there exists an (LF, LF)-partition for any plane graph G when certain conditions on the degree of the internal vertices and their neighbourhoods are satisfied.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 1; 95-102
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Decompositions of quadrangle-free planar graphs
Autorzy:
Borodin, Oleg
Ivanova, Anna
Kostochka, Alexandr
Sheikh, Naeem
Powiązania:
https://bibliotekanauki.pl/articles/743120.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graphs
graph decompositions
quadrangle-free graphs
Opis:
W. He et al. showed that a planar graph not containing 4-cycles can be decomposed into a forest and a graph with maximum degree at most 7. This degree restriction was improved to 6 by Borodin et al. We further lower this bound to 5 and show that it cannot be improved to 3.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 1; 87-99
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Long induced paths in 3-connected planar graphs
Autorzy:
Arocha, Jorge
Valencia, Pilar
Powiązania:
https://bibliotekanauki.pl/articles/743721.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
induced paths
3-connected planar graphs
Opis:
It is shown that every 3-connected planar graph with a large number of vertices has a long induced path.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 1; 105-107
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
An Analogue of DP-Coloring for Variable Degeneracy and its Applications
Autorzy:
Sittitrai, Pongpat
Nakprasit, Kittikorn
Powiązania:
https://bibliotekanauki.pl/articles/32361750.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
DP-colorings
arboricity colorings
planar graphs
Opis:
A graph G is list vertex k-arborable if for every k-assignment L, one can choose f(v) ∈ L(v) for each vertex v so that vertices with the same color induce a forest. In [6], Borodin and Ivanova proved that every planar graph without 4-cycles adjacent to 3-cycles is list vertex 2-arborable. In fact, they proved a more general result in terms of variable degeneracy. Inspired by these results and DP-coloring which is a generalization of list coloring and has become a widely studied topic, we introduce a generalization on variable degeneracy including list vertex arboricity. We use this notion to extend a general result by Borodin and Ivanova. Not only this theorem implies results about planar graphs without 4-cycles adjacent to 3-cycle by Borodin and Ivanova, it also implies other results including a result by Kim and Yu [S.-J. Kim and X. Yu, Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable, Graphs Combin. 35 (2019) 707–718] that every planar graph without 4-cycles adjacent to 3-cycles is DP-4-colorable.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 89-99
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Triangle Decompositions of Planar Graphs
Autorzy:
Mynhardt, Christina M.
Bommel, Christopher M. van
Powiązania:
https://bibliotekanauki.pl/articles/31340823.pdf
Data publikacji:
2016-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graphs
triangle decompositions
rational triangle decompositions
Opis:
A multigraph G is triangle decomposable if its edge set can be partitioned into subsets, each of which induces a triangle of G, and rationally triangle decomposable if its triangles can be assigned rational weights such that for each edge e of G, the sum of the weights of the triangles that contain e equals 1. We present a necessary and sufficient condition for a planar multigraph to be triangle decomposable. We also show that if a simple planar graph is rationally triangle decomposable, then it has such a decomposition using only weights 0, 1 and 1/2 . This result provides a characterization of rationally triangle decomposable simple planar graphs. Finally, if G is a multigraph with K4 as underlying graph, we give necessary and sufficient conditions on the multiplicities of its edges for G to be triangle and rationally triangle decomposable.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 3; 643-659
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Edge Colorings of 1-Planar Graphs without 5-Cycles with Two Chords
Autorzy:
Sun, Lin
Wu, Jianliang
Powiązania:
https://bibliotekanauki.pl/articles/31343454.pdf
Data publikacji:
2019-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
1-planar graphs
edge coloring
discharging method
Opis:
A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that every 1-planar graph with maximum degree ∆ ≥ 8 is edge-colorable with ∆ colors if each of its 5-cycles contains at most one chord.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 2; 301-312
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Linear List Coloring of Some Sparse Graphs
Autorzy:
Chen, Ming
Li, Yusheng
Zhang, Li
Powiązania:
https://bibliotekanauki.pl/articles/32083756.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
linear coloring
maximum average degree
planar graphs
discharging
Opis:
A linear $k$-coloring of a graph is a proper $k$-coloring of the graph such that any subgraph induced by the vertices of any pair of color classes is a union of vertex-disjoint paths. A graph $G$ is linearly $L$-colorable if there is a linear coloring $c$ of $G$ for a given list assignment $L = \{L(v) : v ∈ V(G)\}$ such that $c(v) ∈ L(v)$ for all $v ∈ V(G)$, and $G$ is linearly $k$-choosable if $G$ is linearly $L$-colorable for any list assignment with $|L(v)| ≥ k$. The smallest integer $k$ such that $G$ is linearly $k$-choosable is called the linear list chromatic number, denoted by $lc_l(G)$. It is clear that \(lc_l(G)≥\Big\lceil\frac{\Delta(G)}{1}\Big\rceil+1\) for any graph $G$ with maximum degree $\Delta(G)$. The maximum average degree of a graph $G$, denoted by $mad(G)$, is the maximum of the average degrees of all subgraphs of $G$. In this note, we shall prove the following. Let $G$ be a graph, (1) if $mad(G)<\frac{8}{3}$ and $\Delta(G) ≥ 7$, then \(lc_l(G)=\Big\lceil\frac{\Delta(G)}{2}\Big\rceil+1\); (2) if $mad(G)<{18}{7}$ and $\Delta(G) ≥ 5$, then \(lc_l(G)=\Big\lceil\frac{\Delta(G)}{2}\Big\rceil+1\); (3) if $mad(G)<{20}{7}$ and $\Delta(G) ≥ 5$, then \(lc_l(G)≤\Big\lceil\frac{\Delta(G)}{2}\Big\rceil+2\).
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 51-64
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
List Star Edge-Coloring of Subcubic Graphs
Autorzy:
Kerdjoudj, Samia
Kostochka, Alexandr
Raspaud, André
Powiązania:
https://bibliotekanauki.pl/articles/31342241.pdf
Data publikacji:
2018-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
edge coloring
star coloring
planar graphs
Opis:
A star edge-coloring of a graph $ G $ is a proper edge coloring such that every 2-colored connected subgraph of $ G $ is a path of length at most 3. For a graph $ G $, let the list star chromatic index of $ G $, $ ch_{st}^' (G) $, be the minimum $k$ such that for any $k$-uniform list assignment $L$ for the set of edges, $G$ has a star edge-coloring from L. Dvořák, Mohar and Šámal asked whether the list star chromatic index of every subcubic graph is at most 7. We prove that it is at most 8. We also prove that if the maximum average degree of a subcubic graph $G$ is less than \( \tfrac{7}{3} \) (respectively, \( \tfrac{5}{2} \)), then $ ch_{st}^' (G) \le 5 $ (respectively, $ ch_{st}^' (G) \le 6 $).
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 1037-1054
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Strong chromatic index of planar graphs with large girth
Autorzy:
Jennhwa Chang, Gerard
Montassier, Mickael
Pêche, Arnaud
Raspaud, André
Powiązania:
https://bibliotekanauki.pl/articles/30148715.pdf
Data publikacji:
2014-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graphs
edge coloring
2-distance coloring
strong edgecoloring
Opis:
Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 10Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 4; 723-733
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Paths of low weight in planar graphs
Autorzy:
Fabrici, Igor
Harant, Jochen
Jendrol', Stanislav
Powiązania:
https://bibliotekanauki.pl/articles/743525.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graphs
polytopal graphs
paths
weight of an edge
weight of a path
Opis:
The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are:
1. Every 3-connected simple planar graph G that contains a k-path, a path on k vertices, also contains a k-path P such that for its weight (the sum of degrees of its vertices) in G it holds
$w_G(P): = ∑_{u∈ V(P)} deg_G(u) ≤ (3/2)k² + (k)$
2. Every plane triangulation T that contains a k-path also contains a k-path P such that for its weight in T it holds
$w_T(P): = ∑_{u∈ V(P)} deg_T(u) ≤ k² +13 k$
3. Let G be a 3-connected simple planar graph of circumference c(G). If c(G) ≥ σ| V(G)| for some constant σ > 0 then for any k, 1 ≤ k ≤ c(G), G contains a k-path P such that
$w_G(P) = ∑_{u∈ V(P)} deg_G(u) ≤ (3/σ + 3)k$.
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 1; 121-135
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P3 Problem on Planar Graphs
Autorzy:
Tu, Jianhua
Shi, Yongtang
Powiązania:
https://bibliotekanauki.pl/articles/31343724.pdf
Data publikacji:
2019-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
combinatorial optimization
vertex cover P3 problem
branch- width
planar graphs
EPTAS
Opis:
Given a graph G = (V,E), the task in the vertex cover P3(VCP3) problem is to find a minimum subset of vertices F ⊆ V such that every path of order 3 in G contains at least one vertex from F. The VCP3 problem remains NP-hard even in planar graphs and has many applications in real world. In this paper, we give a dynamic-programming algorithm to solve the VCP3 problem on graphs of bounded branchwidth. Using the dynamic programming algorithm and the Baker’s EPTAS framework for NP-hard problems, we present an efficient polynomial time approximation scheme (EPTAS) for the VCP3 problem on planar graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 55-65
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 17

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies