Grid representations and the chromatic number

DOI10.1016/J.COMGEO.2013.05.003MaRDI QIDQ2391545zbMATHOpenAlexFDO

Authors Martin Balko

Publication date 31 July 2013

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.0210

zbMATH Keywords

gridchromatic numbergraph coloringgraph drawings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: A grid drawing of a graph maps vertices to grid points and edges to line segments that avoid grid points representing other vertices. We show that there is a number of grid points that some line segment of an arbitrary grid drawing must intersect. This number is closely connected to the chromatic number. Second, we study how many columns we need to draw a graph in the grid, introducing some new $NP$-complete problems. Finally, we show that any planar graph has a planar grid drawing where every line segment contains exactly two grid points. This result proves conjectures asked by David Flores-Pe~naloza and Francisco Javier Zaragoza Martinez.

Recommendations

• Grid drawings and the chromatic number
• Reprint of: ``Grid representations and the chromatic number
• On the oriented chromatic number of grids
• On the pushable chromatic number of various types of grids
• A note on the oriented chromatic number of grids
• On the 2-edge-coloured chromatic number of grids
• On the chromatic numbers of signed triangular and hexagonal grids
• Graph of realizations and chromatic numbers
• On some coloring problems in grids
• The incidence chromatic number of toroidal grids

Cites work

• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• Acyclic colorings of planar graphs
• How to draw a planar graph on a grid
• Minimum-width grid drawings of plane graphs
• Splitting a graph into disjoint induced paths or cycles.
• Threshold for path colorings of planar graphs

Cited in

(7)

• The linzertorte problem, or a unified approach to painting, baking and weaving
• Chromatic number for a generalization of Cartesian product graphs
• On the oriented chromatic number of grids
• Grid drawings of \(k\)-colourable graphs
• On the chromatic numbers of signed triangular and hexagonal grids
• Chromatic Numbers of Specified Isohedral Tilings
• Grid drawings and the chromatic number

This page was built for publication: Grid representations and the chromatic number

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