Local \(k\)-colorings of graphs and hypergraphs (Q1095156): Difference between revisions

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. Among the results proved are: Theorem: There exists a graphs with arbitrary chromatic number and a local 2-coloring such that all monochromatic subgraphs are bipartite. Theorem: For all bipartite graphs B and all k there exists a bipartite graph B' such that when B' is locally k-colored, then it contains a monochromatic copy of B as an induced subgraph of B'.