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-27 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ł
    Tytuł:
    Vertex rainbow colorings of graphs
    Autorzy:
    Fujie-Okamoto, Futaba
    Kolasinski, Kyle
    Lin, Jianwei
    Zhang, Ping
    Powiązania:
    https://bibliotekanauki.pl/articles/743667.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    rainbow path
    vertex rainbow coloring
    vertex rainbow connection number
    Opis:
    In a properly vertex-colored graph G, a path P is a rainbow path if no two vertices of P have the same color, except possibly the two end-vertices of P. If every two vertices of G are connected by a rainbow path, then G is vertex rainbow-connected. A proper vertex coloring of a connected graph G that results in a vertex rainbow-connected graph is a vertex rainbow coloring of G. The minimum number of colors needed in a vertex rainbow coloring of G is the vertex rainbow connection number vrc(G) of G. Thus if G is a connected graph of order n ≥ 2, then 2 ≤ vrc(G) ≤ n. We present characterizations of all connected graphs G of order n for which vrc(G) ∈ {2,n-1,n} and study the relationship between vrc(G) and the chromatic number χ(G) of G. For a connected graph G of order n and size m, the number m-n+1 is the cycle rank of G. Vertex rainbow connection numbers are determined for all connected graphs of cycle rank 0 or 1 and these numbers are investigated for connected graphs of cycle rank 2.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 1; 63-80
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Distinguishing Cartesian Products of Countable Graphs
    Autorzy:
    Estaji, Ehsan
    Imrich, Wilfried
    Kalinowski, Rafał
    Pilśniak, Monika
    Tucker, Thomas
    Powiązania:
    https://bibliotekanauki.pl/articles/31342144.pdf
    Data publikacji:
    2017-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    vertex coloring
    distinguishing number
    automorphisms
    infinite graphs
    Cartesian and weak Cartesian product
    Opis:
    The distinguishing number D(G) of a graph G is the minimum number of colors needed to color the vertices of G such that the coloring is preserved only by the trivial automorphism. In this paper we improve results about the distinguishing number of Cartesian products of finite and infinite graphs by removing restrictions to prime or relatively prime factors.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 1; 155-164
    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ł:
    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ł:
    New models and algorithms for RNA pseudoknot order assignment
    Autorzy:
    Zok, Tomasz
    Badura, Jan
    Swat, Sylwester
    Figurski, Kacper
    Popenda, Mariusz
    Antczak, Maciej
    Powiązania:
    https://bibliotekanauki.pl/articles/911230.pdf
    Data publikacji:
    2020
    Wydawca:
    Uniwersytet Zielonogórski. Oficyna Wydawnicza
    Tematy:
    RNA pseudoknot order
    conflict graph
    vertex coloring
    maximum independent set
    integer programming
    kolorowanie grafu
    zbiór niezależny
    programowanie całkowitoliczbowe
    Opis:
    The pseudoknot is a specific motif of the RNA structure that highly influences the overall shape and stability of a molecule. It occurs when nucleotides of two disjoint single-stranded fragments of the same chain, separated by a helical fragment, interact with each other and form base pairs. Pseudoknots are characterized by great topological diversity, and their systematic description is still a challenge. In our previous work, we have introduced the pseudoknot order: a new coefficient representing the topological complexity of the pseudoknotted RNA structure. It is defined as the minimum number of base pair set decompositions, aimed to obtain the unknotted RNA structure. We have suggested how it can be useful in the interpretation and understanding of a hierarchy of RNA folding. However, it is not trivial to unambiguously identify pseudoknots and determine their orders in an RNA structure. Therefore, since the introduction of this coefficient, we have worked on the method to reliably assign pseudoknot orders in correspondence to the mechanisms that control the biological process leading to their formation in the molecule. Here, we introduce a novel graph coloring-based model for the problem of pseudoknot order assignment. We show a specialized heuristic operating on the proposed model and an alternative integer programming algorithm. The performance of both approaches is compared with that of state-of-the-art algorithms which so far have been most efficient in solving the problem in question. We summarize the results of computational experiments that evaluate our new methods in terms of classification quality on a representative data set originating from the non-redundant RNA 3D structure repository.
    Źródło:
    International Journal of Applied Mathematics and Computer Science; 2020, 30, 2; 315-324
    1641-876X
    2083-8492
    Pojawia się w:
    International Journal of Applied Mathematics and Computer Science
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A Note on the Total Detection Numbers of Cycles
    Autorzy:
    Escuadro, Henry E.
    Fujie, Futaba
    Musick, Chad E.
    Powiązania:
    https://bibliotekanauki.pl/articles/31339492.pdf
    Data publikacji:
    2015-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    vertex-distinguishing coloring
    detectable labeling
    detection number
    total detection number
    Hamiltonian graph
    Opis:
    Let G be a connected graph of size at least 2 and c :E(G)→{0, 1, . . ., k− 1} an edge coloring (or labeling) of G using k labels, where adjacent edges may be assigned the same label. For each vertex v of G, the color code of v with respect to c is the k-vector code(v) = (a0, a1, . . ., ak−1), where ai is the number of edges incident with v that are labeled i for 0 ≤ i ≤ k − 1. The labeling c is called a detectable labeling if distinct vertices in G have distinct color codes. The value val(c) of a detectable labeling c of a graph G is the sum of the labels assigned to the edges in G. The total detection number td(G) of G is defined by td(G) = min{val(c)}, where the minimum is taken over all detectable labelings c of G. We investigate the problem of determining the total detection numbers of cycles.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 2; 237-247
    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ł:
    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ł:
    Vertex-Distinguishing IE-Total Colorings of Complete Bipartite Graphs Km,N(m < n)
    Autorzy:
    Chen, Xiang’en
    Gao, Yuping
    Yao, Bing
    Powiązania:
    https://bibliotekanauki.pl/articles/30146641.pdf
    Data publikacji:
    2013-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    complete bipartite graphs
    IE-total coloring
    vertex-distinguishing IE-total coloring
    vertex-distinguishing IE-total chromatic number
    Opis:
    Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C(u) be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt(G), and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. VDIET colorings of complete bipartite graphs Km,n(m < n) are discussed in this paper. Particularly, the VDIET chromatic numbers of Km,n(1 ≤ m ≤ 7, m < n) as well as complete graphs Kn are obtained.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 2; 289-306
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Parity vertex colorings of binomial trees
    Autorzy:
    Gregor, Petr
    Škrekovski, Riste
    Powiązania:
    https://bibliotekanauki.pl/articles/743737.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    binomial tree
    parity coloring
    vertex ranking
    Opis:
    We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 1; 177-180
    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ł:
    Generalized Hypergraph Coloring
    Autorzy:
    Schweser, Thomas
    Powiązania:
    https://bibliotekanauki.pl/articles/32083810.pdf
    Data publikacji:
    2021-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hypergraph decomposition
    vertex partition
    degeneracy
    coloring of hypergraphs
    hypergraph properties
    Opis:
    A smooth hypergraph property \(\mathcal{P}\) is a class of hypergraphs that is hereditary and non-trivial, i.e., closed under induced subhypergraphs and it contains a non-empty hypergraph but not all hypergraphs. In this paper we examine \(\mathcal{P}\)-colorings of hypergraphs with smooth hypergraph properties \(\mathcal{P}\). A \(\mathcal{P}\)-coloring of a hypergraph $H$ with color set $C$ is a function $\varphi : V(H) → C$ such that \(H\big[\varphi^{−1}(c)\big]\) belongs to \(\mathcal{P}\) for all $c ∈ C$. Let $L : V (H) → 2^C$ be a so called list-assignment of the hypergraph $H$. Then, a (\(\mathcal{P}, L\))-coloring of $H$ is a \(\mathcal{P}\)-coloring $\varphi$ of $H$ such that $\varphi(v) ∈ L(v)$ for all $v ∈ V (H)$. The aim of this paper is a characterization of (\(\mathcal{P}, L\))-critical hypergraphs. Those are hypergraphs $H$ such that $H − v$ is (\(\mathcal{P}, L\))-colorable for all $v ∈ V (H)$ but $H$ itself is not. Our main theorem is a Gallai-type result for critical hypergraphs, which implies a Brooks-type result for (\(\mathcal{P}, L\))-colorable hypergraphs. In the last section, we prove a Gallai-type bound for the degree sum of (\(\mathcal{P}, L\))-critical locally simple hypergraphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 1; 103-121
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-27 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