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ł:
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 Note on Neighbor Expanded Sum Distinguishing Index
Autorzy:
Flandrin, Evelyne
Li, Hao
Marczyk, Antoni
Saclé, Jean-François
Woźniak, Mariusz
Powiązania:
https://bibliotekanauki.pl/articles/31342189.pdf
Data publikacji:
2017-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
general edge coloring
total coloring
neighbor-distinguishing index
neighbor sum distinguishing coloring
Opis:
A total k-coloring of a graph G is a coloring of vertices and edges of G using colors of the set [k] = {1, . . ., k}. These colors can be used to distinguish the vertices of G. There are many possibilities of such a distinction. In this paper, we consider the sum of colors on incident edges and adjacent vertices.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 29-37
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ł:
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ł:
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ł:
An Improved Upper Bound on Neighbor Expanded Sum Distinguishing Index
Autorzy:
Vučković, Bojan
Powiązania:
https://bibliotekanauki.pl/articles/32083737.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
general edge coloring
total coloring
neighbor sum distinguishing index
Opis:
A total k-weighting f of a graph G is an assignment of integers from the set {1, . . ., k} to the vertices and edges of G. We say that f is neighbor expanded sum distinguishing, or NESD for short, if Σw∈N(v) (f(vw) + f(w)) differs from Σw∈N(u)(f(uw) + f(w)) for every two adjacent vertices v and u of G. The neighbor expanded sum distinguishing index of G, denoted by egndiΣ(G), is the minimum positive integer k for which there exists an NESD weighting of G. An NESD weighting was introduced and investigated by Flandrin et al. (2017), where they conjectured that egndiΣ(G) ≤ 2 for any graph G. They examined some special classes of graphs, while proving that egndiΣ(G) ≤ χ(G) + 1. We improve this bound and show that egndiΣ(G) ≤ 3 for any graph G. We also show that the conjecture holds for all bipartite, 3-regular and 4-regular graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 323-329
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Antipodal Edge-Colorings of Hypercubes
Autorzy:
West, Douglas B.
Wise, Jennifer I.
Powiązania:
https://bibliotekanauki.pl/articles/31343560.pdf
Data publikacji:
2019-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
antipodal edge-coloring
hypercube
monochromatic geodesic
Opis:
Two vertices of the k-dimensional hypercube Qk are antipodal if they differ in every coordinate. Edges uv and xy are antipodal if u is antipodal to x and v is antipodal to y. An antipodal edge-coloring of Qk is a 2- edge-coloring such that antipodal edges always have different colors. Norine conjectured that for k ≥ 2, in every antipodal edge-coloring of Qk some two antipodal vertices are connected by a monochromatic path. Feder and Subi proved this for k ≤ 5. We prove it for k ≤ 6.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 271-284
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Characterizations of Graphs Having Large Proper Connection Numbers
Autorzy:
Lumduanhom, Chira
Laforge, Elliot
Zhang, Ping
Powiązania:
https://bibliotekanauki.pl/articles/31340917.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge coloring
proper-path coloring
strong proper-path coloring
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 439-453
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ł:
Conflict-Free Connections of Graphs
Autorzy:
Czap, Július
Jendroľ, Stanislav
Valiska, Juraj
Powiązania:
https://bibliotekanauki.pl/articles/31342254.pdf
Data publikacji:
2018-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
conflict-free connection
2-edge-connected graph
tree
Opis:
An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path, which contains a color used on exactly one of its edges. In this paper the question for the smallest number of colors needed for a coloring of edges of G in order to make it conflict-free connected is investigated. We show that the answer is easy for 2-edge-connected graphs and very difficult for other connected graphs, including trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 911-920
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ł
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ł:
Facial [r,s,t]-Colorings of Plane Graphs
Autorzy:
Czap, Július
Šugerek, Peter
Jendrol’, Stanislav
Valiska, Juraj
Powiązania:
https://bibliotekanauki.pl/articles/31343366.pdf
Data publikacji:
2019-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
boundary walk
edge-coloring
vertex-coloring
total-coloring
Opis:
Let $G$ be a plane graph. Two edges are facially adjacent in $G$ if they are consecutive edges on the boundary walk of a face of $G$. Given nonnegative integers $r$, $s$, and $t$, a facial $[r, s, t]$-coloring of a plane graph $G = (V,E)$ is a mapping $f : V \cup E \rightarrow {1, . . ., k} $ such that $ |f(v_1) − f(v_2)| \ge r $ for every two adjacent vertices $ v_1 $ and $ v_2 $, $ | f(e_1) − f(e_2)| \ge s $ for every two facially adjacent edges $ e_1 $ and $ e_2 $, and $ | f(v) − f(e)| \ge t $ for all pairs of incident vertices $ v $ and edges $ e $. The facial $[r, s, t]$-chromatic number $ \overline{ \chi }_{r,s,t} (G) $ of $ G $ is defined to be the minimum $k$ such that $G$ admits a facial $[r, s, t]$-coloring with colors $1, . . ., k$. In this paper we show that $ \overline{ \chi }_{r,s,t} (G) \le 3r + 3s + t + 1 $ for every plane graph $G$. For some triplets $ [r, s, t] $ and for some families of plane graphs this bound is improved. Special attention is devoted to the cases when the parameters $r$, $s$, and $t$ are small.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 629-645
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
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ł
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