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

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  edge coloring
help Sortuj według:

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

A decomposition of gallai multigraphs

100%
Halperin A., Magnant C., Pula K.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 2
331-352
EN
An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed trees
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The upper domination Ramsey number u(4,4)

100%
Dzido T., Zakrzewska R.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 3
419-430
EN
The upper domination Ramsey number u(m,n) is the smallest integer p such that every 2-coloring of the edges of Kₚ with color red and blue, Γ(B) ≥ m or Γ(R) ≥ n, where B and R is the subgraph of Kₚ induced by blue and red edges, respectively; Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. In this paper, we show that u(4,4) ≤ 15.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Multicolor Ramsey numbers for paths and cycles

100%
Dzido T.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
57-65
EN
For given graphs G₁,G₂,...,Gₖ, k ≥ 2, the multicolor Ramsey number R(G₁,G₂,...,Gₖ) is the smallest integer n such that if we arbitrarily color the edges of the complete graph on n vertices with k colors, then it is always a monochromatic copy of some $G_i$, for 1 ≤ i ≤ k. We give a lower bound for k-color Ramsey number R(Cₘ,Cₘ,...,Cₘ), where m ≥ 8 is even and Cₘ is the cycle on m vertices. In addition, we provide exact values for Ramsey numbers R(P₃,Cₘ,Cₚ), where P₃ is the path on 3 vertices, and several values for R(Pₗ,Pₘ,Cₚ), where l,m,p ≥ 2. In this paper we present new results in this field as well as some interesting conjectures.
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

Strong Chromatic Index Of Planar Graphs With Large Girth

80%
Jennhwa Chang G., Montassier M., Pêche A., Raspaud A.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 4
723-733
EN
Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+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.
6
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 ∆.
7
Content available remote

On the Independence Number of Edge Chromatic Critical Graphs

80%
Pang S., Miao L., Song W., Miao Z.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
577-584
EN
In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤ [...] . It is known that α (G) < [...] |V |. In this paper we improve this bound when △≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α (G) ≤ [...] |V | when △ ≥ 5 and n2 ≤ 2(△− 1)
8
Content available remote

Kaleidoscopic Colorings of Graphs

80%
Chartrand G., English S., Zhang P.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
711-727
EN
For an r-regular graph G, let c : E(G) → [k] = {1, 2, . . . , k}, k ≥ 3, be an edge coloring of G, where every vertex of G is incident with at least one edge of each color. For a vertex v of G, the multiset-color cm(v) of v is defined as the ordered k-tuple (a1, a2, . . . , ak) or a1a2 … ak, where ai (1 ≤ i ≤ k) is the number of edges in G colored i that are incident with v. The edge coloring c is called k-kaleidoscopic if cm(u) ≠ cm(v) for every two distinct vertices u and v of G. A regular graph G is called a k-kaleidoscope if G has a k-kaleidoscopic coloring. It is shown that for each integer k ≥ 3, the complete graph Kk+3 is a k-kaleidoscope and the complete graph Kn is a 3-kaleidoscope for each integer n ≥ 6. The largest order of an r-regular 3-kaleidoscope is [...] (r−12) $\left( {\matrix{{r - 1} \cr 2 } } \right)$ . It is shown that for each integer r ≥ 5 such that r ≢ 3 (mod 4), there exists an r-regular 3-kaleidoscope of order [...] (r−12) $\left( {{{r - 1} \over 2}} \right)$ .
9
Content available remote

M2-Edge Colorings Of Cacti And Graph Joins

80%
Czap J., Šugerek P., Ivančo J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
59-69
EN
An edge coloring φ of a graph G is called an M2-edge coloring if |φ(v)| ≤ 2 for every vertex v of G, where φ(v) is the set of colors of edges incident with v. Let 𝒦2(G) denote the maximum number of colors used in an M2-edge coloring of G. In this paper we determine 𝒦2(G) for trees, cacti, complete multipartite graphs and graph joins.
10
Content available remote

Characterizations of Graphs Having Large Proper Connection Numbers

80%
Lumduanhom C., Laforge E., Zhang P.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
439-453
EN
Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u − v path of length d(u, v), then P is a proper u − v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u − v path in G, and c is a strong proper-path coloring if every two vertices u and v are connected by a proper u− v geodesic in G. The minimum number of colors required for a proper-path coloring or strong proper-path coloring of G is called the proper connection number pc(G) or strong proper connection number spc(G) of G, respectively. If G is a nontrivial connected graph of size m, then pc(G) ≤ spc(G) ≤ m and pc(G) = m or spc(G) = m if and only if G is the star of size m. In this paper, we determine all connected graphs G of size m for which pc(G) or spc(G) is m − 1,m − 2 or m − 3.
11
Content available remote

On Twin Edge Colorings of Graphs

80%
Andrews E., Helenius L., Johnston D., VerWys J., Zhang P.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
613-627
EN
A twin edge k-coloring of a graph G is a proper edge coloring of G with the elements of Zk so that the induced vertex coloring in which the color of a vertex v in G is the sum (in Zk) of the colors of the edges incident with v is a proper vertex coloring. The minimum k for which G has a twin edge k-coloring is called the twin chromatic index of G. Among the results presented are formulas for the twin chromatic index of each complete graph and each complete bipartite graph
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles

80%
Cranston D.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 1
163-178
EN
Let G be a planar graph with no two 3-cycles sharing an edge. We show that if Δ(G) ≥ 9, then χ'ₗ(G) = Δ(G) and χ''ₗ(G) = Δ(G)+1. We also show that if Δ(G) ≥ 6, then χ'ₗ(G) ≤ Δ(G)+1 and if Δ(G) ≥ 7, then χ''ₗ(G) ≤ Δ(G)+2. All of these results extend to graphs in the projective plane and when Δ(G) ≥ 7 the results also extend to graphs in the torus and Klein bottle. This second edge-choosability result improves on work of Wang and Lih and of Zhang and Wu. All of our results use the discharging method to prove structural lemmas about the existence of subgraphs with small degree-sum. For example, we prove that if G is a planar graph with no two 3-cycles sharing an edge and with Δ(G) ≥ 7, then G has an edge uv with d(u) ≤ 4 and d(u)+d(v) ≤ Δ(G)+2. All of our proofs yield linear-time algorithms that produce the desired colorings.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On Ramsey $(K_{1,2}, Kₙ)$-minimal graphs

80%
Hałuszczak M.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 2
331-339
EN
Let F be a graph and let 𝓖,𝓗 denote nonempty families of graphs. We write F → (𝓖,𝓗) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is said to be a (𝓖,𝓗)-minimal graph if F → (𝓖,𝓗) and F - e not → (𝓖,𝓗) for every e ∈ E(F). We present a technique which allows to generate infinite family of (𝓖,𝓗)-minimal graphs if we know some special graphs. In particular, we show how to receive infinite family of $(K_{1,2}, Kₙ)$-minimal graphs, for every n ≥ 3.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Interval edge colorings of some products of graphs

80%
Petrosyan P.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
357-373
EN
An edge coloring of a graph G with colors 1,2,...,t is called an interval t-coloring if for each i ∈ {1,2,...,t} there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. A graph G is interval colorable, if there is an integer t ≥ 1 for which G has an interval t-coloring. Let ℜ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if G,H ∈ 𝔑, then the Cartesian product of these graphs belongs to 𝔑. Also, they formulated a similar problem for the lexicographic product as an open problem. In this paper we first show that if G ∈ 𝔑, then G[nK₁] ∈ 𝔑 for any n ∈ ℕ. Furthermore, we show that if G,H ∈ 𝔑 and H is a regular graph, then strong and lexicographic products of graphs G,H belong to 𝔑. We also prove that tensor and strong tensor products of graphs G,H belong to 𝔑 if G ∈ 𝔑 and H is a regular graph.
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On Ramsey $(K_{1,2},C₄)$-minimal graphs

80%
Vetrík T., Yulianti L., Baskoro E.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 4
637-649
EN
For graphs F, G and H, we write F → (G,H) to mean that any red-blue coloring of the edges of F contains a red copy of G or a blue copy of H. The graph F is Ramsey (G,H)-minimal if F → (G,H) but F* ↛ (G,H) for any proper subgraph F* ⊂ F. We present an infinite family of Ramsey $(K_{1,2},C₄)$-minimal graphs of any diameter ≥ 4.
16
Content available remote

The Fan-Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks

71%
Formanowicz P., Tanaś K.
International Journal of Applied Mathematics and Computer Science
|
2012
|
tom 22
|
nr 3
765-778
EN
It was conjectured by Fan and Raspaud (1994) that every bridgeless cubic graph contains three perfect matchings such that every edge belongs to at most two of them. We show a randomized algorithmic way of finding Fan-Raspaud colorings of a given cubic graph and, analyzing the computer results, we try to find and describe the Fan-Raspaud colorings for some selected classes of cubic graphs. The presented algorithms can then be applied to the pair assignment problem in cubic computer networks. Another possible application of the algorithms is that of being a tool for mathematicians working in the field of cubic graph theory, for discovering edge colorings with certain mathematical properties and formulating new conjectures related to the Fan-Raspaud conjecture.
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some applications of pq-groups in graph theory

61%
Exoo G.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 1
109-114
EN
We describe some new applications of nonabelian pq-groups to construction problems in Graph Theory. The constructions include the smallest known trivalent graph of girth 17, the smallest known regular graphs of girth five for several degrees, along with four edge colorings of complete graphs that improve lower bounds on classical Ramsey numbers.
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ć.