Local \(k\)-colorings of graphs and hypergraphs
type: Item
instance of: scholarly article
title: Local \(k\)-colorings of graphs and hypergraphs
zbMATH Open document ID: 0632.05041
DOI: 10.1016/0095-8956(87)90017-7
author: B. George
published in: Journal of Combinatorial Theory. Series B
publication date: 1987-01-01T00:00:00Z
review text: 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'.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 4027512
zbMATH Keywords: edge-coloring
zbMATH Keywords: Ramsey theory
zbMATH Keywords: local k-coloring
zbMATH Keywords: chromatic number
zbMATH Keywords: bipartite graphs
zbMATH Keywords: monochromatic copy
zbMATH Keywords: induced subgraph
reviewed by: John Mitchem
MaRDI profile type: Publication
full work available at URL: 0095-8956(87)90017-7
OpenAlex ID: W2056006353
cites work: Even edge colorings of a graph
cites work: On size Ramsey number of paths, trees, and circuits. I
cites work: Q3852212
cites work: Q3937444
cites work: Monochromatic paths in edge-colored graphs
cites work: The Ramsey number of a graph with bounded maximum degree
cites work: Q4056030
cites work: The size Ramsey number
cites work: Coloring graphs with locally few colors
cites work: Q5596772
cites work: Q4071274
cites work: Q5545303
cites work: Q3903002
cites work: A Ramsey-type problem in directed and bipartite graphs
cites work: Ramsey numbers for local colorings
cites work: The biparticity of a graph
cites work: Q5525916
cites work: The Ramsey property for graphs with forbidden complete subgraphs
cites work: The structure of critical Ramsey graphs
cites work: Two proofs of the Ramsey property of the class of finite hypergraphs
cites work: Q4103565
cites work: Nombre chromatique et plus longs chemins d'un graphe
cites work: Q4177585
cites work: Q5750908
cites work: Q5790850
description: scientific article; zbMATH DE number 4027512