Results 1 to 10 of about 4,035 (167)
On splittable colorings of graphs and hypergraphs [PDF]
Journal of Graph Theory, 2002 AbstractA multigraph is (k,r)‐dense if every k‐set spans at most r edges. What is the maximum number of edges exℕ(n,k,r) in a (k,r)‐dense multigraph on n vertices? We determine the maximum possible weight of such graphs for almost all k and r (e.g., for all r>k3) by determining a constant m=m(k,r) and showing that exℕ(n,k,r)=m$\left ( n\atop 2\right
Zoltán Füredi, Radhika Ramamurthi
semanticscholar +14 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 ...
Alexandr Kostochka, Xuding Zhu
semanticscholar +4 more sources
Coloring the hypergraph of maximal cliques of a graph with no long path
Discrete Mathematics, 2003 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Sylvain Gravier +2 more
semanticscholar +4 more sources
Bounded colorings of multipartite graphs and hypergraphs
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
Nina Kamčev, Benny Sudakov, Jan Volec
core +7 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.
András Gyárfás +5 more
semanticscholar +5 more sources
Equipartite colorings in graphs and hypergraphs
Journal of Combinatorial Theory, Series B, 1977 C. Berge, F. Sterboul
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
Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs [PDF]
SIAM Journal on Discrete Mathematics, 2013 We investigate the relationship between two kinds of vertex colorings of hypergraphs: unique-maximum colorings and conflict-free colorings. In a unique-maximum coloring, the colors are ordered, and in every hyperedge of the hypergraph the maximum color appears only once. In a conflict-free coloring, in every hyperedge of the hypergraph there is a color
Panagiotis Cheilaris +2 more
+8 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)\}|$.
Michael Anastos, Alan Frieze
+8 more sources
Graph Entropy Based on Strong Coloring of Uniform Hypergraphs [PDF]
Axioms, 2021 The classical graph entropy based on the vertex coloring proposed by Mowshowitz depends on a graph. In fact, a hypergraph, as a generalization of a graph, can express complex and high-order relations such that it is often used to model complex systems. Being different from the classical graph entropy, we extend this concept to a hypergraph.
Lusheng Fang +3 more
openalex +3 more sources