The plane-width of graphs

Marcin Kamiński, Paul Medvedev, Martin Milanič

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish (US)
Pages (from-to)229-245
Number of pages17
JournalJournal of Graph Theory
Volume68
Issue number3
DOIs
StatePublished - Nov 2011

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'The plane-width of graphs'. Together they form a unique fingerprint.

Cite this