The Plane-Width of Graphs

Details The Plane-Width of Graphs The Plane-Width of Graphs

2008-12-23

arxiv.org/abs/0812.4346v1

Computer Science

Discrete Mathematics

Scientific paper

Map vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least a unit distance apart. The plane-width of a graph is the minimum diameter of the image of the vertex set over all such mappings. We establish a relation between the plane-width of a graph and its chromatic number, and connect it to other well-known areas, including the circular chromatic number and the problem of packing unit discs in the plane. We also investigate how plane-width behaves under various operations, such as homomorphism, disjoint union, complement, and the Cartesian product.

Affiliated with

Also associated with

No associations

Rating

The Plane-Width of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Plane-Width of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Plane-Width of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-605744