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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 27
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ł:
A note on vertex colorings of plane graphs
Autorzy:
Fabrici, Igor
Jendrol’, Stanislav
Soták, Roman
Powiązania:
https://bibliotekanauki.pl/articles/30148722.pdf
Data publikacji:
2014-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
vertex coloring
Opis:
Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V, let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 4; 849-855
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Star Coloring of Subcubic Graphs
Autorzy:
Karthick, T.
Subramanian, C.R.
Powiązania:
https://bibliotekanauki.pl/articles/30146582.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
vertex coloring
star coloring
subcubic graphs
Opis:
A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on 4 vertices is bi-colored. The star chromatic number of G, χs(G), is the minimum number of colors needed to star color G. In this paper, we show that if a graph G is either non-regular subcubic or cubic with girth at least 6, then χs(G) ≤ 6, and the bound can be realized in linear time.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 373-385
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ł:
On multiset colorings of graphs
Autorzy:
Okamoto, Futaba
Salehi, Ebrahim
Zhang, Ping
Powiązania:
https://bibliotekanauki.pl/articles/744555.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
vertex coloring
multiset coloring
neighbor-distinguishing coloring
Opis:
A vertex coloring of a graph G is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum k for which G has a multiset k-coloring is the multiset chromatic number χₘ(G) of G. For every graph G, χₘ(G) is bounded above by its chromatic number χ(G). The multiset chromatic numbers of regular graphs are investigated. It is shown that for every pair k, r of integers with 2 ≤ k ≤ r - 1, there exists an r-regular graph with multiset chromatic number k. It is also shown that for every positive integer N, there is an r-regular graph G such that χ(G) - χₘ(G) = N. In particular, it is shown that χₘ(Kₙ × K₂) is asymptotically √n. In fact, $χₘ(Kₙ × K₂) = χₘ(cor(K_{n+1}))$. The corona cor(G) of a graph G is the graph obtained from G by adding, for each vertex v in G, a new vertex v' and the edge vv'. It is shown that χₘ(cor(G)) ≤ χₘ(G) for every nontrivial connected graph G. The multiset chromatic numbers of the corona of all complete graphs are determined. On Multiset Colorings of Graphs From this, it follows that for every positive integer N, there exists a graph G such that χₘ(G) - χₘ(cor(G)) ≥ N. The result obtained on the multiset chromatic number of the corona of complete graphs is then extended to the corona of all regular complete multipartite graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 1; 137-153
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ł:
On Efficient coloring of chordless graphs
Autorzy:
Janczewski, R.
Małafiejski, M.
Powiązania:
https://bibliotekanauki.pl/articles/375900.pdf
Data publikacji:
2009
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
vertex coloring
chordless graphs
chromatic number
Opis:
We are given a simple graph G = (V,E). Any edge e ∈ E is a chord in a path P ⊆ G (cycle C ⊆ G) iff a graph obtained by joining e to path P (cycle C) has exactly two vertices of degree 3. A class of graphs without any chord in paths (cycles) we call pathchordless (cycle-chordless). We will prove that recognizing and coloring of these graphs can be done in O(n2) and O(n) time, respectively. Our study was motivated by a wide range of applications of the graph coloring problem in coding theory, time tabling and scheduling, frequency assignment, register allocation and many other areas.
Źródło:
Decision Making in Manufacturing and Services; 2009, 3, 1-2; 5-14
1896-8325
2300-7087
Pojawia się w:
Decision Making in Manufacturing and Services
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Colorings of Plane Graphs Without Long Monochromatic Facial Paths
Autorzy:
Czap, Július
Fabrici, Igor
Jendrol’, Stanislav
Powiązania:
https://bibliotekanauki.pl/articles/32222689.pdf
Data publikacji:
2021-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
facial path
vertex-coloring
Opis:
Let G be a plane graph. A facial path of G is a subpath of the boundary walk of a face of G. We prove that each plane graph admits a 3-coloring (a 2-coloring) such that every monochromatic facial path has at most 3 vertices (at most 4 vertices). These results are in a contrast with the results of Chartrand, Geller, Hedetniemi (1968) and Axenovich, Ueckerdt, Weiner (2017) which state that for any positive integer t there exists a 4-colorable (a 3-colorable) plane graph Gt such that in any its 3-coloring (2-coloring) there is a monochromatic path of length at least t. We also prove that every plane graph is 2-list-colorable in such a way that every monochromatic facial path has at most 4 vertices.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 3; 801-808
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Grundy number of graphs
Autorzy:
Effantin, Brice
Kheddouci, Hamamache
Powiązania:
https://bibliotekanauki.pl/articles/743619.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Grundy coloring
vertex coloring
cartesian product
graph product
Opis:
The Grundy number of a graph G is the maximum number k of colors used to color the vertices of G such that the coloring is proper and every vertex x colored with color i, 1 ≤ i ≤ k, is adjacent to (i-1) vertices colored with each color j, 1 ≤ j ≤ i -1. In this paper we give bounds for the Grundy number of some graphs and cartesian products of graphs. In particular, we determine an exact value of this parameter for n-dimensional meshes and some n-dimensional toroidal meshes. Finally, we present an algorithm to generate all graphs for a given Grundy number.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 1; 5-18
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
3-consecutive c-colorings of graphs
Autorzy:
Bujtás, Csilla
Sampathkumar, E.
Tuza, Zsolt
Subramanya, M.
Dominic, Charles
Powiązania:
https://bibliotekanauki.pl/articles/744032.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
vertex coloring
consecutive coloring
upper chromatic number
Opis:
A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number $(χ̅)_{3CC}(G)$ of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with $(χ̅)_{3CC}(G) ≥ k$ for k = 3 and k = 4.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 3; 393-405
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ł:
Erdős regular graphs of even degree
Autorzy:
Dobrynin, Andrey
Mel'nikov, Leonid
Pyatkin, Artem
Powiązania:
https://bibliotekanauki.pl/articles/743782.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
vertex coloring
4-critical graph
circulant
regular graph
vertex connectivity
Opis:
In 1960, Dirac put forward the conjecture that r-connected 4-critical graphs exist for every r ≥ 3. In 1989, Erdös conjectured that for every r ≥ 3 there exist r-regular 4-critical graphs. A method for finding r-regular 4-critical graphs and the numbers of such graphs for r ≤ 10 have been reported in [6,7]. Results of a computer search for graphs of degree r = 12,14,16 are presented. All the graphs found are both r-regular and r-connected.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 2; 269-279
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Conflict-Free Vertex-Connections of Graphs
Autorzy:
Li, Xueliang
Zhang, Yingying
Zhu, Xiaoyu
Mao, Yaping
Zhao, Haixing
Jendrol’, Stanislav
Powiązania:
https://bibliotekanauki.pl/articles/31868621.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
vertex-coloring
conflict-free vertex-connection
2-connected graph
tree
Opis:
A path in a vertex-colored graph is called conflict-free if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be conflict-free vertex-connected if any two vertices of the graph are connected by a conflict-free path. This paper investigates the question: for a connected graph G, what is the smallest number of colors needed in a vertex-coloring of G in order to make G conflict-free vertex-connected. As a result, we get that the answer is easy for 2-connected graphs, and very difficult for connected graphs with more cut-vertices, including trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 51-65
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Rainbow Vertex-Connection
Autorzy:
Li, Xueliang
Shi, Yongtang
Powiązania:
https://bibliotekanauki.pl/articles/30146636.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow vertex-connection
vertex coloring
minimum degree
2-step dominating set
Opis:
A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph $G$, denoted by $rvc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. It was proved that if $G$ is a graph of order $n$ with minimum degree $ \delta $, then $ rvc(G) < 11n//\delta$. In this paper, we show that $rvc(G) \le 3n//(δ+1)+5$ for $ \delta \ge \sqrt{n-1} -1 $ and $ n \le 290 $, while $ rvc(G) \le 4n//(δ + 1) + 5 $ for $ 16 \le \delta \le \sqrt{n-1}-2 $ and $ rvc(G) \le 4n//(\delta + 1) + C(\delta) $ for $6 \le \delta \le 15$, where $ C(\delta) = e^\frac{ 3 \log (\delta^3 + 2 \delta^2 +3)-3(\log 3 - 1)}{\delta - 3} - 2$. We also prove that $ rvc(G) \le 3n//4 − 2 $ for $ \delta = 3$, $ rvc(G) \le 3n//5 − 8//5$ for $\delta = 4$ and $rvc(G) \le n//2 − 2$ for $\delta = 5$. Moreover, an example constructed by Caro et al. shows that when $ \delta \ge \sqrt{n-1} - 1 $ and $ \delta = 3, 4, 5 $, our bounds are seen to be tight up to additive constants.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 307-313
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Vertex-Rainbow Index of A Graph
Autorzy:
Mao, Yaping
Powiązania:
https://bibliotekanauki.pl/articles/31340818.pdf
Data publikacji:
2016-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
vertex-coloring
connectivity
vertex-rainbow S-tree
vertex- rainbow index
Nordhaus-Gaddum type
Opis:
The k-rainbow index rxk(G) of a connected graph G was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the k-rainbow index, we introduce the concept of k-vertex-rainbow index rvxk(G) in this paper. In this paper, sharp upper and lower bounds of rvxk(G) are given for a connected graph G of order n, that is, 0 ≤ rvxk(G) ≤ n − 2. We obtain Nordhaus-Gaddum results for 3-vertex-rainbow index of a graph G of order n, and show that rvx3(G) + rvx3(Ḡ) = 4 for n = 4 and 2 ≤ rvx3(G) + rvx3(Ḡ) ≤ n − 1 for n ≥ 5. Let t(n, k, ℓ) denote the minimal size of a connected graph G of order n with rvxk(G) ≤ ℓ, where 2 ≤ ℓ ≤ n − 2 and 2 ≤ k ≤ n. Upper and lower bounds on t(n, k, ℓ) are also obtained.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 3; 669-681
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 27

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