Acyclic and k-distance coloring of the grid

DOI10.1016/S0020-0190(03)00232-1MaRDI QIDQ1014392zbMATH OpenOpenAlexFDO

Authors Guillaume Fertin, Emmanuel Godard, André 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

\(d\)-dimensional grids\(k\)-distance coloringacyclic coloringgraph algorithmshypercubes

Mathematics Subject Classification ID

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

Recommendations

• Optimal Acyclic Edge Colouring of Grid Like Graphs
• Optimal acyclic edge colouring of grid like graphs
• Acyclic coloring of graphs
• On the acyclic chromatic number of Hamming graphs
• Acyclic coloring of graphs of maximum degree

Cites work

• A coloring problem on the \(n\)-cube
• Acyclic colorings of planar graphs
• Acyclic Colourings of Planar Graphs with Large Girth
• scientific article; zbMATH DE number 3616457 (Why is no real title available?)
• On acyclic colorings of planar graphs
• Star coloring of graphs
• The Chromatic Number of Graph Powers
• The chromatic number of oriented graphs

Cited in

(37)

• On the acyclic chromatic number of Hamming graphs
• The linzertorte problem, or a unified approach to painting, baking and weaving
• Coloring of the \(d^{\text{th}}\) power of the face-centered cubic grid
• Star colouring of bounded degree graphs and regular graphs
• 2-edge-colored chromatic number of grids is at most 9
• A survey on packing colorings
• Signed coloring of 2-dimensional grids
• L(p,q) labeling of d-dimensional grids
• Acyclic coloring of graphs of maximum degree five: nine colors are enough
• Chromatic number for a generalization of Cartesian product graphs
• Acyclic vertex coloring of graphs of maximum degree six
• A survey on the distance-colouring of graphs
• A note on \(S\)-packing colorings of lattices
• Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions
• Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets
• Grid Colorings in Steganography
• Optimal Acyclic Edge Colouring of Grid Like Graphs
• Coloring, location and domination of corona graphs
• Impartial coloring games
• Acyclic homomorphisms to stars of graph Cartesian products and chordal bipartite graphs
• scientific article; zbMATH DE number 1735785 (Why is no real title available?)
• On the connectivity of k-distance graphs
• On the 2-edge-coloured chromatic number of grids
• A polyhedral study of the acyclic coloring problem
• Hardness transitions and uniqueness of acyclic colouring
• Computation of the von Neumann entropy of large matrices via trace estimators and rational Krylov methods
• Acyclic vertex coloring of graphs of maximum degree 5
• Coloring of graphs avoiding bicolored paths of a fixed length
• On the independence number of graph powers
• Star colouring and locally constrained graph homomorphisms
• Acyclic colorings of graphs with obstructions
• Grid drawings of \(k\)-colourable graphs
• Optimal acyclic edge colouring of grid like graphs
• The distance coloring of graphs
• The 2-distance coloring of the Cartesian product of cycles using optimal Lee codes
• Acyclic colorings of products of trees
• On colorings of graph fractional powers

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

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