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: 14

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  plane graph
help Sortuj według:

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

A Note On Vertex Colorings Of Plane Graphs

100%
Fabricia I., Jendrol’ S., Soták R.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 4
849-855
EN
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.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On doubly light vertices in plane graphs

100%
Kozáková V., Madaras T.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
333-344
EN
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.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Note on the weight of paths in plane triangulations of minimum degree 4 and 5

80%
Madaras T.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 2
173-180
EN
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.
4
Content available remote

Decompositions of Plane Graphs Under Parity Constrains Given by Faces

80%
Czap J., Tuza Z.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
521-530
EN
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?
5
Content available remote

A note on face coloring entire weightings of plane graphs

80%
Jendrol S., Šugerek P.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 2
421-426
EN
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
6
Content available remote

An Extension of Kotzig’s Theorem

80%
Aksenov V. A., Borodin O. V., Ivanova A. O.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 4
889-897
EN
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.
7
Content available remote

Unique-Maximum Coloring Of Plane Graphs

80%
Fabrici I., Göring F.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
95-102
EN
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.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the strong parity chromatic number

80%
Czap J., Jendroľ S., Kardoš F.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 3
587-600
EN
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.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the structure of plane graphs of minimum face size 5

80%
Madaras T.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
403-411
EN
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.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A note on cyclic chromatic number

80%
Zlámalová J.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 1
115-122
EN
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.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Unavoidable set of face types for planar maps

71%
Horňák M., Jendrol S.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 2
123-141
EN
The type of a face f of a planar map is a sequence of degrees of vertices of f as they are encountered when traversing the boundary of f. A set 𝒯 of face types is found such that in any normal planar map there is a face with type from 𝒯. The set 𝒯 has four infinite series of types as, in a certain sense, the minimum possible number. An analogous result is applied to obtain new upper bounds for the cyclic chromatic number of 3-connected planar maps.
12
Content available remote

WORM Colorings of Planar Graphs

71%
Czap J., Jendrol’ S., Valiska J.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 2
353-368
EN
Given three planar graphs F,H, and G, an (F,H)-WORM coloring of G is a vertex coloring such that no subgraph isomorphic to F is rainbow and no subgraph isomorphic to H is monochromatic. If G has at least one (F,H)-WORM coloring, then W−F,H(G) denotes the minimum number of colors in an (F,H)-WORM coloring of G. We show that (a) W−F,H(G) ≤ 2 if |V (F)| ≥ 3 and H contains a cycle, (b) W−F,H(G) ≤ 3 if |V (F)| ≥ 4 and H is a forest with Δ (H) ≥ 3, (c) W−F,H(G) ≤ 4 if |V (F)| ≥ 5 and H is a forest with 1 ≤ Δ (H) ≤ 2. The cases when both F and H are nontrivial paths are more complicated; therefore we consider a relaxation of the original problem. Among others, we prove that any 3-connected plane graph (respectively outerplane graph) admits a 2-coloring such that no facial path on five (respectively four) vertices is monochromatic.
13
Content available remote

On the Weight of Minor Faces in Triangle-Free 3-Polytopes

71%
Borodin O. V., Ivanova A. O.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
603-619
EN
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.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Colouring vertices of plane graphs under restrictions given by faces

61%
Czap J., Jendrol' S.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
521-543
EN
We consider a vertex colouring of a connected plane graph G. A colour c is used k times by a face α of G if it appears k times along the facial walk of α. We prove that every connected plane graph with minimum face degree at least 3 has a vertex colouring with four colours such that every face uses some colour an odd number of times. We conjecture that such a colouring can be done using three colours. We prove that this conjecture is true for 2-connected cubic plane graphs. Next we consider other three kinds of colourings that require stronger restrictions.
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ć.