Locally restricted colorings

DOI10.1016/J.DAM.2005.05.012MaRDI QIDQ2581565zbMATH OpenOpenAlexFDO

Authors Ivo Blöchliger, Dominique De Werra

Publication date 10 January 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.05.012

zbMATH Keywords

chromatic numbergraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

Let \(G\) be a graph with chromatic number \(\chi \geq 2.\) It is not difficult to see that for each \(\chi \)-coloring of \(G\) there is a vertex \(v\;\)so that each color occurs on some neighbour of \(v.\) It is shown in the paper that this property does not extend to \(k\)-colorings of \(G\) with \(k>\chi .\) Let \( \rho (\chi ,p)\) be the smallest number \(\rho \) so that for any graph \(G\) with chromatic number \(\chi \) and any coloring of \(G\) with \(\chi +p\) colors there is a vertex \(v\) so that at least \(\chi \) different collors occur at distance at most \(\rho \) from \(v.\) The authors prove that for all \(\chi \) and \(p\) it is \(\rho (\chi ,p)\leq \lceil \frac{p}{2}\rceil +1.\)

Recommendations

• scientific article; zbMATH DE number 1885944
• Coloring graphs with locally few colors
• On coloring graphs with locally small chromatic number
• Extending graph colorings
• scientific article; zbMATH DE number 2077673

Cites work

• scientific article; zbMATH DE number 426339 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 3262991 (Why is no real title available?)
• On some properties of suboptimal colorings of graphs
• Variations on the Roy-Gallai theorem

Cited in

(5)

• A generalization of the Erdős-Ko-Rado theorem
• Locality of not-so-weak coloring
• Local coloring: new observations and new reductions
• Obstructions to locally injective oriented improper colourings
• On some properties of suboptimal colorings of graphs

This page was built for publication: Locally restricted colorings

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