Local rainbow colorings

DOI10.4310/JOC.2011.V2.N2.A6MaRDI QIDQ433480zbMATH OpenOpenAlexFDO

Authors Noga Alon, Ido Ben-Eliezer

Publication date 16 July 2012

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4310/joc.2011.v2.n2.a6

zbMATH Keywords

edge-coloringsrainbow colorings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Review text

From the authors' abstract:NEWLINENEWLINE``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(K_n)\) with \(k\) colors, each associated with one of the vertices of \(K_n\), such that for every copy \(T\) of \(H\) in \(K_n\) at least one of the colorings that are associated with \(V(T)\) assigns distinct colors to all the edges of \(E(T)\).NEWLINENEWLINEWe characterize the set of all graphs \(H\) for which \(C(n,H)\) is bounded by some absolute constant \(c(H)\), prove a general upper bound, and obtain lower and upper bounds for several graphs of special interest. A special case of our results partially answers an extremal question of Karchmer and Wigderson motivated by the investigation of the computational power of span programs.

Recommendations

• Ramsey numbers for local colorings
• Locally rainbow graphs
• Local edge colorings that are global
• scientific article; zbMATH DE number 2077673
• scientific article; zbMATH DE number 5995288

Cited in

(4)

• Localized query: color spanning variations
• scientific article; zbMATH DE number 881158 (Why is no real title available?)
• Local rainbow colorings for various graphs
• On locally rainbow colourings

This page was built for publication: Local rainbow colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q433480)