Acyclic and \(k\)-distance coloring of the grid

DOI10.1016/S0020-0190(03)00232-1zbMath1175.68293OpenAlexW1976536763MaRDI QIDQ1014392

Emmanuel Godard, Guillaume Fertin, Andre Raspaud

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(03)00232-1

zbMATH Keywords

hypercubesgraph algorithmsacyclic coloring\(d\)-dimensional grids\(k\)-distance coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (26)

Star colouring of bounded degree graphs and regular graphs ⋮ \(L(p,q)\) labeling of \(d\)-dimensional grids ⋮ Acyclic colorings of products of trees ⋮ Acyclic coloring of graphs of maximum degree five: nine colors are enough ⋮ Unnamed Item ⋮ A note on \(S\)-packing colorings of lattices ⋮ Coloring, location and domination of corona graphs ⋮ Impartial coloring games ⋮ A survey on packing colorings ⋮ Acyclic vertex coloring of graphs of maximum degree 5 ⋮ Hardness transitions and uniqueness of acyclic colouring ⋮ Computation of the von Neumann entropy of large matrices via trace estimators and rational Krylov methods ⋮ Acyclic homomorphisms to stars of graph Cartesian products and chordal bipartite graphs ⋮ Acyclic vertex coloring of graphs of maximum degree six ⋮ A survey on the distance-colouring of graphs ⋮ On colorings of graph fractional powers ⋮ A polyhedral study of the acyclic coloring problem ⋮ Coloring of graphs avoiding bicolored paths of a fixed length ⋮ Coloring of the \(d^{\text{th}}\) power of the face-centered cubic grid ⋮ Signed coloring of 2-dimensional grids ⋮ The distance coloring of graphs ⋮ Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions ⋮ On the acyclic chromatic number of Hamming graphs ⋮ The 2-distance coloring of the Cartesian product of cycles using optimal Lee codes ⋮ On the connectivity of k-distance graphs ⋮ Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets

Cites Work

• Unnamed Item
• On acyclic colorings of planar graphs
• A coloring problem on the \(n\)-cube
• Star coloring of graphs
• Acyclic Colourings of Planar Graphs with Large Girth
• The Chromatic Number of Graph Powers
• The chromatic number of oriented graphs
• Acyclic colorings of planar graphs

This page was built for publication: Acyclic and \(k\)-distance coloring of the grid