Grid representations and the chromatic number

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

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

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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• How to draw a planar graph on a grid
• Splitting a graph into disjoint induced paths or cycles.
• Minimum-width grid drawings of plane graphs
• Acyclic colorings of planar graphs

Cited In (4)

• On the oriented chromatic number of grids
• Chromatic Numbers of Specified Isohedral Tilings
• On the chromatic numbers of signed triangular and hexagonal grids
• Grid drawings of \(k\)-colourable graphs

Recommendations

• Title not available (Why is that?) 👍 👎
• On the oriented chromatic number of grids 👍 👎
• A note on the oriented chromatic number of grids 👍 👎
• The incidence chromatic number of toroidal grids 👍 👎
• Reprint of: ``Grid representations and the chromatic number 👍 👎
• On some coloring problems in grids 👍 👎
• On the chromatic numbers of signed triangular and hexagonal grids 👍 👎
• Grid Drawings and the Chromatic Number 👍 👎
• On the pushable chromatic number of various types of grids 👍 👎
• Graph of realizations and chromatic numbers 👍 👎

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)