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ę "plane graph" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 28
Tytuł:
A note on vertex colorings of plane graphs
Autorzy:
Fabrici, Igor
Jendrol’, Stanislav
Soták, Roman
Powiązania:
https://bibliotekanauki.pl/articles/30148722.pdf
Data publikacji:
2014-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
vertex coloring
Opis:
Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V, let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 4; 849-855
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the structure of plane graphs of minimum face size 5
Autorzy:
Madaras, Tomás
Powiązania:
https://bibliotekanauki.pl/articles/744532.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
light graph
face size
Opis:
A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is known that a plane graph of minimum face size 5 contains light paths and a light pentagon. In this paper we show that every plane graph of minimum face size 5 contains also a light star $K_{1,3}$ and we present a structural result concerning the existence of a pair of adjacent faces with degree-bounded vertices.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 403-411
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On doubly light vertices in plane graphs
Autorzy:
Kozáková, Veronika
Madaras, Tomáš
Powiązania:
https://bibliotekanauki.pl/articles/743891.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
doubly light vertex
Opis:
A vertex is said to be doubly light in a family of plane graphs if its degree and sizes of neighbouring faces are bounded above by a finite constant. We provide several results on the existence of doubly light vertices in various families of plane graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 2; 333-344
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Minimal unavoidable sets of cycles in plane graphs
Autorzy:
Madaras, T.
Tamasova, M.
Powiązania:
https://bibliotekanauki.pl/articles/255251.pdf
Data publikacji:
2018
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
plane graph
polyhedral graph
set of cycles
Opis:
A set S of cycles is minimal unavoidable in a graph family [formula] if each graph [formula] contains a cycle from S and, for each proper subset S' ⊂ S, there exists an infinite subfamily [formula] such that no graph from [formula] contains a cycle from S'. In this paper, we study minimal unavoidable sets of cycles in plane graphs of minimum degree at least 3 and present several graph constructions which forbid many cycle sets to be unavoidable. We also show the minimality of several small sets consisting of short cycles
Źródło:
Opuscula Mathematica; 2018, 38, 6; 859-870
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Decompositions of Plane Graphs Under Parity Constrains Given by Faces
Autorzy:
Czap, Július
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/30146456.pdf
Data publikacji:
2013-07-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
parity partition
edge coloring
Opis:
An edge coloring of a plane graph G is facially proper if no two faceadjacent edges of G receive the same color. A facial (facially proper) parity edge coloring of a plane graph G is an (facially proper) edge coloring with the property that, for each color c and each face f of G, either an odd number of edges incident with f is colored with c, or color c does not occur on the edges of f. In this paper we deal with the following question: For which integers k does there exist a facial (facially proper) parity edge coloring of a plane graph G with exactly k colors?
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 3; 521-530
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on face coloring entire weightings of plane graphs
Autorzy:
Jendrol, Stanislav
Šugerek, Peter
Powiązania:
https://bibliotekanauki.pl/articles/31232002.pdf
Data publikacji:
2014-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
entire weighting
plane graph
face colouring
Opis:
Given a weighting of all elements of a 2-connected plane graph $G = (V,E, F)$, let $f(α)$ denote the sum of the weights of the edges and vertices incident with the face α and also the weight of α. Such an entire weighting is a proper face colouring provided that $f(α) ≠ f(β)$ for every two faces α and β sharing an edge. We show that for every 2-connected plane graph there is a proper face-colouring entire weighting with weights 1 through 4. For some families we improved 4 to 3.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 2; 421-426
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Survey on the Cyclic Coloring and its Relaxations
Autorzy:
Czap, Július
Horňák, Mirko
Jendroľ, Stanislav
Powiązania:
https://bibliotekanauki.pl/articles/32083738.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
edge coloring
vertex coloring
Opis:
A cyclic coloring of a plane graph is a vertex coloring such that any two vertices incident with the same face receive distinct colors. This type of coloring was introduced more than fifty years ago, and a lot of research in chromatic graph theory was sparked by it. This paper is a survey on the state of the art concerning the cyclic coloring and relaxations of this graph invariant.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 5-38
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Colorings of Plane Graphs Without Long Monochromatic Facial Paths
Autorzy:
Czap, Július
Fabrici, Igor
Jendrol’, Stanislav
Powiązania:
https://bibliotekanauki.pl/articles/32222689.pdf
Data publikacji:
2021-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
facial path
vertex-coloring
Opis:
Let G be a plane graph. A facial path of G is a subpath of the boundary walk of a face of G. We prove that each plane graph admits a 3-coloring (a 2-coloring) such that every monochromatic facial path has at most 3 vertices (at most 4 vertices). These results are in a contrast with the results of Chartrand, Geller, Hedetniemi (1968) and Axenovich, Ueckerdt, Weiner (2017) which state that for any positive integer t there exists a 4-colorable (a 3-colorable) plane graph Gt such that in any its 3-coloring (2-coloring) there is a monochromatic path of length at least t. We also prove that every plane graph is 2-list-colorable in such a way that every monochromatic facial path has at most 4 vertices.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 3; 801-808
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Facial rainbow edge-coloring of simple 3-connected plane graphs
Autorzy:
Czap, Julius
Powiązania:
https://bibliotekanauki.pl/articles/255771.pdf
Data publikacji:
2020
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
plane graph
facial path
edge-coloring
Opis:
A facial rainbow edge-coloring of a plane graph G is an edge-coloring such that any two edges receive distinct colors if they lie on a common facial path of G. The minimum number of colors used in such a coloring is denoted by erb(G). Trivially, erb(G) ≥ L(G) + 1 holds for every plane graph without cut-vertices, where L(G) denotes the length of a longest facial path in G. Jendrol’ in 2018 proved that every simple 3-connected plane graph admits a facial rainbow edge-coloring with at most L(G) + 2 colors, moreover, this bound is tight for L(G) = 3. He also proved that erb(G) = L(G) + 1 for L(G) ∉ {3,4, 5}. He posed the following conjecture: There is a simple 3-connected plane graph G with L(G) = 4 and erb(G) = L(G) + 2. In this note we answer the conjecture in the affirmative. Keywords: plane graph, facial path, edge-coloring.
Źródło:
Opuscula Mathematica; 2020, 40, 4; 475-482
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Note on the weight of paths in plane triangulations of minimum degree 4 and 5
Autorzy:
Madaras, Tomás
Powiązania:
https://bibliotekanauki.pl/articles/743763.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
weight of path
plane graph
triangulation
Opis:
The weight of a path in a graph is defined to be the sum of degrees of its vertices in entire graph. It is proved that each plane triangulation of minimum degree 5 contains a path P₅ on 5 vertices of weight at most 29, the bound being precise, and each plane triangulation of minimum degree 4 contains a path P₄ on 4 vertices of weight at most 31.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 2; 173-180
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
An Extension of Kotzig’s Theorem
Autorzy:
Aksenov, Valerii A.
Borodin, Oleg V.
Ivanova, Anna O.
Powiązania:
https://bibliotekanauki.pl/articles/31340608.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
normal plane map
structural property
weight
Opis:
In 1955, Kotzig proved that every 3-connected planar graph has an edge with the degree sum of its end vertices at most 13, which is tight. An edge uv is of type (i, j) if d(u) ≤ i and d(v) ≤ j. Borodin (1991) proved that every normal plane map contains an edge of one of the types (3, 10), (4, 7), or (5, 6), which is tight. Cole, Kowalik, and Škrekovski (2007) deduced from this result by Borodin that Kotzig’s bound of 13 is valid for all planar graphs with minimum degree δ at least 2 in which every d-vertex, d ≥ 12, has at most d − 11 neighbors of degree 2. We give a common extension of the three above results by proving for any integer t ≥ 1 that every plane graph with δ ≥ 2 and no d-vertex, d ≥ 11+t, having more than d − 11 neighbors of degree 2 has an edge of one of the following types: (2, 10+t), (3, 10), (4, 7), or (5, 6), where all parameters are tight.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 889-897
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on cyclic chromatic number
Autorzy:
Zlámalová, Jana
Powiązania:
https://bibliotekanauki.pl/articles/744549.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
cyclic colouring
cyclic chromatic number
Opis:
A cyclic colouring of a graph G embedded in a surface is a vertex colouring of G in which any two distinct vertices sharing a face receive distinct colours. The cyclic chromatic number $χ_c(G)$ of G is the smallest number of colours in a cyclic colouring of G. Plummer and Toft in 1987 conjectured that $χ_c(G) ≤ Δ* + 2$ for any 3-connected plane graph G with maximum face degree Δ*. It is known that the conjecture holds true for Δ* ≤ 4 and Δ* ≥ 18. The validity of the conjecture is proved in the paper for some special classes of planar graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 1; 115-122
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Unique-Maximum Coloring Of Plane Graphs
Autorzy:
Fabrici, Igor
Göring, Frank
Powiązania:
https://bibliotekanauki.pl/articles/31341171.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
weak-parity coloring
unique-maximum coloring
Opis:
A unique-maximum k-coloring with respect to faces of a plane graph G is a coloring with colors 1, . . ., k so that, for each face of G, the maximum color occurs exactly once on the vertices of α. We prove that any plane graph is unique-maximum 3-colorable and has a proper unique-maximum coloring with 6 colors.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 95-102
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Weight of Minor Faces in Triangle-Free 3-Polytopes
Autorzy:
Borodin, Oleg V.
Ivanova, Anna O.
Powiązania:
https://bibliotekanauki.pl/articles/31340872.pdf
Data publikacji:
2016-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane map
plane graph
3-polytope
structural property
weight of face
Opis:
The weight w(f) of a face f in a 3-polytope is the degree-sum of vertices incident with f. It follows from Lebesgue’s results of 1940 that every triangle-free 3-polytope without 4-faces incident with at least three 3-vertices has a 4-face with w ≤ 21 or a 5-face with w ≤ 17. Here, the bound 17 is sharp, but it was still unknown whether 21 is sharp. The purpose of this paper is to improve this 21 to 20, which is best possible.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 3; 603-619
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the strong parity chromatic number
Autorzy:
Czap, Július
Jendroľ, Stanislav
Kardoš, František
Powiązania:
https://bibliotekanauki.pl/articles/743985.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
k-planar graph
vertex colouring
strong parity vertex colouring
Opis:
A vertex colouring of a 2-connected plane graph G is a strong parity vertex colouring if for every face f and each colour c, the number of vertices incident with f coloured by c is either zero or odd. Czap et al. in [9] proved that every 2-connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 3; 587-600
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 28

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