Results 1 to 10 of about 13,534 (196)
Hardness of Rainbow Coloring Hypergraphs [PDF]
, 2018 A hypergraph is k-rainbow colorable if there exists a vertex coloring using k colors such that each hyperedge has all the k colors. Unlike usual hypergraph coloring, rainbow coloring becomes harder as the number of colors increases. This work studies the
Guruswami, Venkatesan, Saket, Rishi
core +5 more sources
On Rainbow Antimagic Coloring of Joint Product of Graphs
Cauchy: Jurnal Matematika Murni dan Aplikasi, 2023 Let be a connected graph with vertex set and edge set . A bijection from to the set is a labeling of graph . The bijection is called rainbow antimagic vertex labeling if for any two edge and in path , where and .
Brian Juned Septory +3 more
doaj +2 more sources
Optimal Colorings with Rainbow Paths [PDF]
Graphs and Combinatorics, 2017 Let $G$ be a connected graph of chromatic number $k$. For a $k$-coloring $f$ of $G$, a full $f$-rainbow path is a path of order $k$ in $G$ whose vertices are all colored differently by $f$. We show that $G$ has a $k$-coloring $f$ such that every vertex
Bendele, Oliver, Rautenbach, Dieter
core +2 more sources
Color code techniques in rainbow connection [PDF]
Electronic Journal of Graph Theory and Applications, 2018 Let G be a graph with an edge k-coloring γ : E(G) → {1, …, k} (not necessarily proper). A path is called a rainbow path if all of its edges have different colors.
Fendy Septyanto, Kiki A. Sugeng
doaj +2 more sources
Journal of Combinatorics, 2011 Given a graph H, we denote by C(n,H) the minimum number k such that the following holds. There are n colorings of E(Kn) with k-colors, each associated with one of the vertices of Kn, such that for every copy T of H in Kn, at least one of the colorings that are associated with V (T ) assigns distinct colors to all the edges of E(T ). We characterize the
Noga Alon, Ido Ben‐Eliezer
openalex +2 more sources
On the fine-grained complexity of rainbow coloring [PDF]
, 2016 The Rainbow k-Coloring problem asks whether the edges of a given graph can be colored in $k$ colors so that every pair of vertices is connected by a rainbow path, i.e., a path with all edges of different colors.
Kowalik, Łukasz +2 more
core +5 more sources
Rainbow connections of bioriented graphs [PDF]
HeliyonFor a directed graph D, it's deemed rainbow connected if each arc is assigned a different color, so that all paths from the vertex u to the vertex v are rainbow connected.
Linlin Wang, Sujuan Liu, Han Jiang
doaj +2 more sources
Schur numbers involving rainbow colorings
Ars Mathematica Contemporanea, 2020 Summary: In this paper, we introduce two different generalizations of Schur numbers that involve rainbow colorings. Motivated by well-known generalizations of Ramsey numbers, we first define the rainbow Schur number \(RS(n)\) to be the minimum number of colors needed such that every coloring of \(\{1,2,\dots,n\}\), in which all available colors are ...
Mark Budden
openalex +4 more sources
Computing Minimum Rainbow and Strong Rainbow Colorings of Block Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 A path in an edge-colored graph $G$ is rainbow if no two edges of it are colored the same. The graph $G$ is rainbow-connected if there is a rainbow path between every pair of vertices. If there is a rainbow shortest path between every pair of vertices, the graph $G$ is strongly rainbow-connected.
Melissa Keranen, Juho Lauri
openalex +7 more sources
Facial Rainbow Coloring of Plane Graphs
Discussiones Mathematicae Graph Theory, 2019 A vertex coloring of a plane graph G is a facial rainbow coloring if any two vertices of G connected by a facial path have distinct colors. The facial rainbow number of a plane graph G, denoted by rb(G), is the minimum number of colors that are necessary
Jendroľ Stanislav, Kekeňáková Lucia
doaj +2 more sources