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

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

Wyniki wyszukiwania

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

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A note on the Ramsey number and the planar Ramsey number for C₄ and complete graphs

100%
Bielak H.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
135-142
EN
We give a lower bound for the Ramsey number and the planar Ramsey number for C₄ and complete graphs. We prove that the Ramsey number for C₄ and K₇ is 21 or 22. Moreover we prove that the planar Ramsey number for C₄ and K₆ is equal to 17.
2
Content available remote

On Longest Cycles in Essentially 4-Connected Planar Graphs

100%
Fabrici I., Harant J., Jendroľ S.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
565-575
EN
A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that [...] . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover, new lower bounds on the length of a longest cycle of G are presented if G is an essentially 4-connected planar graph of maximum degree 4 or G is an essentially 4-connected maximal planar graph.
3
Content available remote

A Note on Barnette’s Conjecture

80%
Harant J.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
133-137
EN
Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

An inequality concerning edges of minor weight in convex 3-polytopes

80%
Fabrici I., Jendrol' S.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 1
81-87
EN
Let $e_{ij}$ be the number of edges in a convex 3-polytope joining the vertices of degree i with the vertices of degree j. We prove that for every convex 3-polytope there is $20e_{3,3} + 25e_{3,4} + 16e_{3,5} + 10e_{3,6} + 6[2/3]e_{3,7} + 5e_{3,8} + 2[1/2]e_{3,9} + 2e_{3,10} + 16[2/3]e_{4,4} + 11e_{4,5} + 5e_{4,6} + 1[2/3]e_{4,7} + 5[1/3]e_{5,5} + 2e_{5,6} ≥ 120$; moreover, each coefficient is the best possible. This result brings a final answer to the conjecture raised by B. Grünbaum in 1973.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On light subgraphs in plane graphs of minimum degree five

80%
Jendrol' S., Madaras T.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 2
207-217
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 well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars $K_{1,3}$ and $K_{1,4}$ and a light 4-path P₄. The results obtained for $K_{1,3}$ and P₄ are best possible.
6
Content available remote

Light Graphs In Planar Graphs Of Large Girth

80%
Hudák P., Maceková M., Madaras T., Široczki P.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
227-238
EN
A graph H is defined to be light in a graph family 𝒢 if there exist finite numbers φ(H, 𝒢) and w(H, 𝒢) such that each G ∈ 𝒢 which contains H as a subgraph, also contains its isomorphic copy K with ΔG(K) ≤ φ(H, 𝒢) and ∑x∈V(K) degG(x) ≤ w(H, 𝒢). In this paper, we investigate light graphs in families of plane graphs of minimum degree 2 with prescribed girth and no adjacent 2-vertices, specifying several necessary conditions for their lightness and providing sharp bounds on φ and w for light K1,3 and C10.
7
Content available remote

Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs

80%
Borodin O. V., Ivanova A. O.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 4
759-770
EN
We prove that every planar graph with maximum degree ∆ is strong edge (2∆−1)-colorable if its girth is at least 40 [...] +1. The bound 2∆−1 is reached at any graph that has two adjacent vertices of degree ∆.
8
Content available remote

Strong Edge-Coloring Of Planar Graphs

80%
Song W.-Y., Miao L.-Y.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 4
845-857
EN
A strong edge-coloring of a graph is a proper edge-coloring where each color class induces a matching. We denote by 𝜒's(G) the strong chromatic index of G which is the smallest integer k such that G can be strongly edge-colored with k colors. It is known that every planar graph G has a strong edge-coloring with at most 4 Δ(G) + 4 colors [R.J. Faudree, A. Gyárfás, R.H. Schelp and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205–211]. In this paper, we show that if G is a planar graph with g ≥ 5, then 𝜒's(G) ≤ 4(G) − 2 when Δ(G) ≥ 6 and 𝜒's(G) ≤ 19 when Δ(G) = 5, where g is the girth of G.
9
Content available remote

All Tight Descriptions of 3-Stars in 3-Polytopes with Girth 5

80%
Borodin O. V., Ivanova A. O.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
5-12
EN
Lebesgue (1940) proved that every 3-polytope P5 of girth 5 has a path of three vertices of degree 3. Madaras (2004) refined this by showing that every P5 has a 3-vertex with two 3-neighbors and the third neighbor of degree at most 4. This description of 3-stars in P5s is tight in the sense that no its parameter can be strengthened due to the dodecahedron combined with the existence of a P5 in which every 3-vertex has a 4-neighbor. We give another tight description of 3-stars in P5s: there is a vertex of degree at most 4 having three 3-neighbors. Furthermore, we show that there are only these two tight descriptions of 3-stars in P5s. Also, we give a tight description of stars with at least three rays in P5s and pose a problem of describing all such descriptions. Finally, we prove a structural theorem about P5s that might be useful in further research.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some totally 4-choosable multigraphs

80%
Woodall D.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
425-455
EN
It is proved that if G is multigraph with maximum degree 3, and every submultigraph of G has average degree at most 2(1/2) and is different from one forbidden configuration C⁺₄ with average degree exactly 2(1/2), then G is totally 4-choosable; that is, if every element (vertex or edge) of G is assigned a list of 4 colours, then every element can be coloured with a colour from its own list in such a way that no two adjacent or incident elements are coloured with the same colour. This shows that the List-Total-Colouring Conjecture, that ch''(G) = χ''(G) for every multigraph G, is true for all multigraphs of this type. As a consequence, if G is a graph with maximum degree 3 and girth at least 10 that can be embedded in the plane, projective plane, torus or Klein bottle, then ch''(G) = χ''(G) = 4. Some further total choosability results are discussed for planar graphs with sufficiently large maximum degree and girth.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The list linear arboricity of planar graphs

80%
An X., Wu B.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
499-510
EN
The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. An and Wu introduce the notion of list linear arboricity lla(G) of a graph G and conjecture that lla(G) = la(G) for any graph G. We confirm that this conjecture is true for any planar graph having Δ ≥ 13, or for any planar graph with Δ ≥ 7 and without i-cycles for some i ∈ {3,4,5}. We also prove that ⌈½Δ(G)⌉ ≤ lla(G) ≤ ⌈½(Δ(G)+1)⌉ for any planar graph having Δ ≥ 9.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Planar Ramsey numbers

80%
Gorgol I.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
45-50
EN
The planar Ramsey number PR(G,H) is defined as the smallest integer n for which any 2-colouring of edges of Kₙ with red and blue, where red edges induce a planar graph, leads to either a red copy of G, or a blue H. In this note we study the weak induced version of the planar Ramsey number in the case when the second graph is complete.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On 3-simplicial vertices in planar graphs

80%
Boros E., Jamison R., Laskar R., Mulder H.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
413-421
EN
A vertex v in a graph G = (V,E) is k-simplicial if the neighborhood N(v) of v can be vertex-covered by k or fewer complete graphs. The main result of the paper states that a planar graph of order at least four has at least four 3-simplicial vertices of degree at most five. This result is a strengthening of the classical corollary of Euler's Formula that a planar graph of order at least four contains at least four vertices of degree at most five.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Note on partitions of planar graphs

80%
Broere I., Wilson B., Bucko J.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
211-215
EN
Chartrand and Kronk in 1969 showed that there are planar graphs whose vertices cannot be partitioned into two parts inducing acyclic subgraphs. In this note we show that the same is true even in the case when one of the partition classes is required to be triangle-free only.
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Planar graphs without 4-, 5- and 8-cycles are 3-colorable

80%
Mondal S.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 4
775-789
EN
In this paper we prove that every planar graph without 4, 5 and 8-cycles is 3-colorable.
16
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

4-chromatic Koester graphs

80%
Dobrynin A., Mel'nikov L.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 4
617-627
EN
Let G be a simple 4-regular plane graph and let S be a decomposition of G into edge-disjoint cycles. Suppose that every two adjacent edges on a face belong to different cycles of S. Such a graph G arises as a superposition of simple closed curves in the plane with tangencies disallowed. Studies of coloring of graphs of this kind were originated by Grötzsch. Two 4-chromatic graphs generated by circles in the plane were constructed by Koester in 1984 [10,11,12]. Until now, no other examples of such graphs were known. We present fourteen new 4-chromatic graphs generated by circles in the plane.
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

2-distance 4-colorability of planar subcubic graphs with girth at least 22

80%
Borodin O., Ivanova A.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 1
141-151
EN
The trivial lower bound for the 2-distance chromatic number χ₂(G) of any graph G with maximum degree Δ is Δ+1. It is known that χ₂ = Δ+1 if the girth g of G is at least 7 and Δ is large enough. There are graphs with arbitrarily large Δ and g ≤ 6 having χ₂(G) ≥ Δ+2. We prove the 2-distance 4-colorability of planar subcubic graphs with g ≥ 22.
18
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six

80%
Bu Y., Lih K.-W., Wang W.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 3
429-439
EN
An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge-coloring o G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by χ'ₐ(G). We prove that χ'ₐ(G) is at most the maximum degree plus 2 if G is a planar graph without isolated edges whose girth is at least 6. This gives new evidence to a conjecture proposed in [Z. Zhang, L. Liu, and J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett., 15 (2002) 623-626.]
19
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4

80%
Hasheminezhad M., McKay B.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 1
123-136
EN
We describe how the simple planar quadrangulations with vertices of degree 3 and 4, whose duals are known as octahedrites, can all be obtained from an elementary family of starting graphs by repeatedly applying two expansion operations. This allows for construction of a linear time generator of all graphs in the class with at most a given order, up to isomorphism.
20
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Analogues of cliques for oriented coloring

80%
Klostermeyer W., MacGillivray G.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
373-387
EN
We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.
first rewind previous Strona / 2 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ć.