Results 1 to 10 of about 4,061 (147)
Bounded colorings of multipartite graphs and hypergraphs [PDF]
European Journal of Combinatorics, 2017 Let $c$ be an edge-coloring of the complete $n$-vertex graph $K_n$. The problem of finding properly colored and rainbow Hamilton cycles in $c$ was initiated in 1976 by Bollob s and Erd\H os and has been extensively studied since then. Recently it was extended to the hypergraph setting by Dudek, Frieze and Ruci ski. We generalize these results, giving
Kamčev, Nina +2 more
core +7 more sources
On splittable colorings of graphs and hypergraphs [PDF]
Journal of Graph Theory, 2002 AbstractThe notion of a split coloring of a complete graph was introduced by Erdős and Gyárfás [7] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an adversary.
Füredi, Zoltán, Ramamurthi, Radhika
semanticscholar +4 more sources
Local k-colorings of graphs and hypergraphs
Journal of Combinatorial Theory, Series B, 1987 A local k-coloring of a graph is a coloring of its edges such that the edges incident with any vertex are colored with at most k different colors. In this paper similarities and differences between usual and local k-coloring are investigated with respect to Ramsey type problems.
Gyárfás, A +5 more
semanticscholar +4 more sources
Adapted List Coloring of Graphs and Hypergraphs [PDF]
SIAM Journal on Discrete Mathematics, 2008 We introduce and study adapted list coloring of graphs and hypergraphs. This is a generalization of ordinary list coloring and adapted coloring, and has more applications than these. We prove that the upper bounds on the adaptable choosability of graphs and uniform hypergraphs in terms of maximum degree are sufficiently stronger than those on the ...
A. V. Kostochka, Xuding Zhu
semanticscholar +3 more sources
On generalized colorings and color functions of graphs and hypergraphs
Meiqiao Zhang
semanticscholar +4 more sources
Cartesian product of hypergraphs: properties and algorithms [PDF]
Electronic Proceedings in Theoretical Computer Science, 2009 Cartesian products of graphs have been studied extensively since the 1960s. They make it possible to decrease the algorithmic complexity of problems by using the factorization of the product.
Alain Bretto +2 more
doaj +6 more sources
On the connectivity threshold for colorings of random graphs and hypergraphs [PDF]
, 2018 Let $ _q= _q(H)$ denote the set of proper $[q]$-colorings of the hypergraph $H$. Let $ _q$ be the graph with vertex set $ _q$ and an edge ${ , \}$ where $ , $ are colorings iff $h( , )=1$. Here $h( , )$ is the Hamming distance $|\{v\in V(H): (v)\neq (v)\}|$.
Anastos, Michael, Frieze, Alan
+7 more sources
Colorings of hypergraphs, perfect graphs, and associated primes of powers of monomial ideals [PDF]
Journal of Algebra, 2011 20 pages; v2 contains relatively minor changes in presentation and updated references.
Francisco, Christopher A. +2 more
+6 more sources
Coloring [Formula: see text]-Embeddable [Formula: see text]-Uniform Hypergraphs. [PDF]
Discrete Comput Geom, 2014 This paper extends the scenario of the Four Color Theorem in the following way. Let H(d,k) be the set of all k-uniform hypergraphs that can be (linearly) embedded into R^d.
Heise CG +3 more
europepmc +3 more sources
On the connectivity of proper colorings of random graphs and hypergraphs
Random Structures & Algorithms, 2020 Let Ωq=Ωq(H) denote the set of proper [q]‐colorings of the hypergraph H. Let Γq be the graph with vertex set Ωq where two colorings σ,τ are adjacent iff the corresponding colorings differ in exactly one vertex. We show that if H=Hn,m;k, k ≥ 2, the random k‐uniform hypergraph with V=[n] and m=dn/k hyperedges then w.h.p.
Anastos, Michael, Frieze, Alan
openaire +4 more sources