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ł:
Spanning trees with many or few colors in edge-colored graphs
Autorzy:
Broersma, Hajo
Li, Xueliang
Powiązania:
https://bibliotekanauki.pl/articles/971955.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
spanning tree
matroid (intersection)
complexity
NP-complete
NP-hard
polynomial algorithm
(minimum) dominating set
Opis:
Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 2; 259-269
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ł:
Some applications of pq-groups in graph theory
Autorzy:
Exoo, Geoffrey
Powiązania:
https://bibliotekanauki.pl/articles/744429.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Ramsey number
edge coloring
cage
degree
girth
Cayley graph
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 1; 109-114
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ł:
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ł:
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ł:
On Ramsey $(K_{1,2},C₄)$-minimal graphs
Autorzy:
Vetrík, Tomás
Yulianti, Lyra
Baskoro, Edy
Powiązania:
https://bibliotekanauki.pl/articles/744084.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Ramsey-minimal graph
edge coloring
diameter of a graph
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 4; 637-649
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ł:
Adjacent vertex distinguishing edge colorings of the direct product of a regular graph by a path or a cycle
Autorzy:
Frigerio, Laura
Lastaria, Federico
Salvi, Norma
Powiązania:
https://bibliotekanauki.pl/articles/743981.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chromatic index
adjacent vertex distinguishing edge coloring
direct product
matching
Opis:
In this paper we investigate the minimum number of colors required for a proper edge coloring of a finite, undirected, regular graph G in which no two adjacent vertices are incident to edges colored with the same set of colors. In particular, we study this parameter in relation to the direct product of G by a path or a cycle.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 3; 547-557
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ł
Tytuł:
Color-bounded hypergraphs, V: host graphs and subdivisions
Autorzy:
Bujtás, Csilla
Tuza, Zsolt
Voloshin, Vitaly
Powiązania:
https://bibliotekanauki.pl/articles/743863.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
mixed hypergraph
color-bounded hypergraph
vertex coloring
arboreal hypergraph
hypertree
feasible set
host graph
edge subdivision
Opis:
A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = {E₁,...,Eₘ}, together with integers $s_i$ and $t_i$ satisfying $1 ≤ s_i ≤ t_i ≤ |E_i|$ for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge $E_i$ satisfies $s_i ≤ |φ(E_i)| ≤ t_i$. The hypergraph ℋ is colorable if it admits at least one proper coloring.
We consider hypergraphs ℋ over a "host graph", that means a graph G on the same vertex set X as ℋ, such that each $E_i$ induces a connected subgraph in G. In the current setting we fix a graph or multigraph G₀, and assume that the host graph G is obtained by some sequence of edge subdivisions, starting from G₀.
The colorability problem is known to be NP-complete in general, and also when restricted to 3-uniform "mixed hypergraphs", i.e., color-bounded hypergraphs in which $|E_i| = 3$ and $1 ≤ s_i ≤ 2 ≤ t_i ≤ 3$ holds for all i ≤ m. We prove that for every fixed graph G₀ and natural number r, colorability is decidable in polynomial time over the class of r-uniform hypergraphs (and more generally of hypergraphs with $|E_i| ≤ r$ for all 1 ≤ i ≤ m) having a host graph G obtained from G₀ by edge subdivisions. Stronger bounds are derived for hypergraphs for which G₀ is a tree.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 2; 223-238
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Interval edge colorings of some products of graphs
Autorzy:
Petrosyan, Petros
Powiązania:
https://bibliotekanauki.pl/articles/743918.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge coloring
interval coloring
regular graph
products of graphs
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 2; 357-373
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Ramsey $(K_{1,2}, Kₙ)$-minimal graphs
Autorzy:
Hałuszczak, Mariusz
Powiązania:
https://bibliotekanauki.pl/articles/743336.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Ramsey minimal graph
edge coloring
1-factor
complete graph
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 2; 331-339
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Almost-Rainbow Edge-Colorings of Some Small Subgraphs
Autorzy:
Krop, Elliot
Krop, Irina
Powiązania:
https://bibliotekanauki.pl/articles/30097998.pdf
Data publikacji:
2013-09-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Ramsey theory
generalized Ramsey theory
rainbow-coloring
edge-coloring
Erdös problem
Opis:
Let $ f(n, p, q) $ be the minimum number of colors necessary to color the edges of $ K_n $ so that every $ K_p $ is at least $ q $-colored. We improve current bounds on these nearly “anti-Ramsey” numbers, first studied by Erdös and Gyárfás. We show that $ f(n, 5, 0) \ge \frac{7}{4} n - 3 $, slightly improving the bound of Axenovich. We make small improvements on bounds of Erdös and Gyárfás by showing $ \frac{5}{6} n + 1 \leq f(n,4,5) $ and for all even $ n ≢ 1(\text{mod } 3) $, $ f(n, 4, 5) \leq n−1 $. For a complete bipartite graph $ G= K_{n,n}$, we show an $n$-color construction to color the edges of $ G $ so that every $ C_4 ⊆ G $ is colored by at least three colors. This improves the best known upper bound of Axenovich, Füredi, and Mubayi.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 4; 771-784
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
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ł
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