Abstract
Map the vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least unit distance apart. The plane-width of a graph is the minimum diameter of the image of its vertex set over all such mappings. We establish a relation between the plane-width of a graph and its chromatic number. We also connect it to other well-known areas, including the circular chromatic number and the problem of packing unit discs in the plane.
Original language | English (US) |
---|---|
Pages (from-to) | 229-245 |
Number of pages | 17 |
Journal | Journal of Graph Theory |
Volume | 68 |
Issue number | 3 |
DOIs | |
State | Published - Nov 2011 |
All Science Journal Classification (ASJC) codes
- Geometry and Topology