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ę "edge coloring" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 51
Tytuł:
Maximum Edge-Colorings Of Graphs
Autorzy:
Jendrol’, Stanislav
Vrbjarová, Michaela
Powiązania:
https://bibliotekanauki.pl/articles/31341153.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
r -maximum k -edge-coloring
unique-maximum edge-coloring
weak-odd edge-coloring
weak-even edge-coloring
Opis:
An $r$-maximum $k$-edge-coloring of $G$ is a $k$-edge-coloring of $G$ having a property that for every vertex $v$ of degree $d_G(v) = d, d \ge r$, the maximum color, that is present at vertex $v$, occurs at $v$ exactly $r$ times. The $r$-maximum index $ \chi_r^′ (G) $ is defined to be the minimum number $k$ of colors needed for an $r$-maximum $k$-edge-coloring of graph $G$. In this paper we show that $ \chi_r^′ (G) \le 3 $ for any nontrivial connected graph $G$ and $ r = 1$ or 2. The bound 3 is tight. All graphs $G$ with $ \chi_1^' (G) =i $, $i = 1, 2, 3$ are characterized. The precise value of the $r$-maximum index, $ r \ge 1 $, is determined for trees and complete graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 117-125
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Three edge-coloring conjectures
Autorzy:
Schelp, Richard
Powiązania:
https://bibliotekanauki.pl/articles/743559.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
Ramsey number
vertex-distinguishing edge-coloring
strong chromatic index
balanced edge-coloring
local coloring
mean coloring
Opis:
The focus of this article is on three of the author's open conjectures. The article itself surveys results relating to the conjectures and shows where the conjectures are known to hold.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 173-182
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On twin edge colorings of graphs
Autorzy:
Andrews, Eric
Helenius, Laars
Johnston, Daniel
VerWys, Jonathon
Zhang, Ping
Powiązania:
https://bibliotekanauki.pl/articles/30148690.pdf
Data publikacji:
2014-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge coloring
vertex coloring
factorization
Opis:
A twin edge $k$-coloring of a graph $G$ is a proper edge coloring of $G$ with the elements of $\mathbb{Z}_k$ so that the induced vertex coloring in which the color of a vertex $v$ in $G$ is the sum (in $\mathbb{Z}_k$) 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
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 3; 613-627
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Vertex-distinguishing edge-colorings of linear forests
Autorzy:
Cichacz, Sylwia
Przybyło, Jakub
Powiązania:
https://bibliotekanauki.pl/articles/744522.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
irregular edge-coloring
vertex-distinguishing edge-coloring
point-distinguishing chromatic index
Opis:
In the PhD thesis by Burris (Memphis (1993)), a conjecture was made concerning the number of colors c(G) required to edge-color a simple graph G so that no two distinct vertices are incident to the same multiset of colors. We find the exact value of c(G) - the irregular coloring number, and hence verify the conjecture when G is a vertex-disjoint union of paths. We also investigate the point-distinguishing chromatic index, χ₀(G), where sets, instead of multisets, are required to be distinct, and determine its value for the same family of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 1; 95-103
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Multicolor Ramsey numbers for paths and cycles
Autorzy:
Dzido, Tomasz
Powiązania:
https://bibliotekanauki.pl/articles/744302.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge coloring
Ramsey number
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 57-65
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A decomposition of Gallai multigraphs
Autorzy:
Halperin, Alexander
Magnant, Colton
Pula, Kyle
Powiązania:
https://bibliotekanauki.pl/articles/30148236.pdf
Data publikacji:
2014-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge coloring
Gallai multigraph
Opis:
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
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 2; 331-352
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ł:
Kaleidoscopic Colorings of Graphs
Autorzy:
Chartrand, Gary
English, Sean
Zhang, Ping
Powiązania:
https://bibliotekanauki.pl/articles/31341692.pdf
Data publikacji:
2017-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge coloring
vertex coloring
kaleidoscopic coloring
kaleidoscope
Opis:
For an $r$-regular graph $G$, let $ c : E(G) \rightarrow [k] = {1, 2, . . ., k}$, $ k \ge 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 $ c_m(v)$ of $v$ is defined as the ordered $k$-tuple $ (a_1, a_2, . . ., a_k) $ or $ a_1a_2…a_k$, where $a_i$ $(1 \le i \le k)$ is the number of edges in $G$ colored $i$ that are incident with $v$. The edge coloring $c$ is called $k$-kaleidoscopic if $ c_m(u) \ne c_m(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 \ge 3 $, the complete graph $ K_{k+3}$ is a $k$-kaleidoscope and the complete graph $ K_n $ is a 3-kaleidoscope for each integer $ n \ge 6 $. The largest order of an $r$-regular 3-kaleidoscope is \( \binom{r-1}{2} \). It is shown that for each integer $ r \ge 5 $ such that \( r \not\equiv 3 (\text{mod } 4) \), there exists an $r$-regular 3-kaleidoscope of order \( \binom{r-1}{2} \).
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 711-727
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
M2-Edge Colorings Of Cacti And Graph Joins
Autorzy:
Czap, Július
Šugerek, Peter
Ivančo, Jaroslav
Powiązania:
https://bibliotekanauki.pl/articles/31341176.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cactus
edge coloring
graph join
Opis:
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 K2(G) denote the maximum number of colors used in an M2-edge coloring of G. In this paper we determine K2(G) for trees, cacti, complete multipartite graphs and graph joins.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 59-69
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles
Autorzy:
Cranston, Daniel
Powiązania:
https://bibliotekanauki.pl/articles/743133.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
list coloring
edge coloring
total coloring
Vizing's Conjecture
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 1; 163-178
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ł:
M2-edge colorings of dense graphs
Autorzy:
Ivanco, J.
Powiązania:
https://bibliotekanauki.pl/articles/254913.pdf
Data publikacji:
2016
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
edge coloring
dominating set
dense graphs
Opis:
An edge coloring φ of a graph G is called an Mi-edge coloring if [formula] every vertex v of G, where φ (v) is the set of colors of edges incident with v. Let K1(G) denote the maximum number of colors used in an Mi-edge coloring of G. In this paper we establish some bounds of K.2(G), present some graphs achieving the bounds and determine exact values of K.2(G) for dense graphs.
Źródło:
Opuscula Mathematica; 2016, 36, 5; 603-612
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
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ł:
The upper domination Ramsey number u(4,4)
Autorzy:
Dzido, Tomasz
Zakrzewska, Renata
Powiązania:
https://bibliotekanauki.pl/articles/743589.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge coloring
upper domination Ramsey number
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 3; 419-430
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six
Autorzy:
Bu, Yuehua
Lih, Ko-Wei
Wang, Weifan
Powiązania:
https://bibliotekanauki.pl/articles/743930.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
vertex-distinguishing
planar graph
Opis:
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.]
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 3; 429-439
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 51

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