Grid representations and the chromatic number

DOI10.1016/J.COMGEO.2013.05.003zbMATH Open1269.05079arXiv1204.0210OpenAlexW2964044475MaRDI QIDQ2391545FDOQ2391545

Authors: Martin Balko 

Publication date: 31 July 2013

Published in: Computational Geometry (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

gridchromatic numbergraph coloringgraph drawings

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• How to draw a planar graph on a grid
• Title not available (Why is that?)
• Splitting a graph into disjoint induced paths or cycles.
• Minimum-width grid drawings of plane graphs
• Threshold for path colorings of planar graphs
• Acyclic colorings of planar graphs

Cited In (7)

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

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)