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