✦ LIBER ✦

The plane-width of graphs

✍ Scribed by Marcin Kamiński; Paul Medvedev; Martin Milanič

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 192 KB
Volume: 68
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20554

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Rank-width of random graphs

✍ Choongbum Lee; Joonkyung Lee; Sang-il Oum 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB

Rank-width of a graph G, denoted by rw(G), is a width parameter of graphs introduced by Oum and Seymour [J Combin Theory Ser B 96 (2006), 514-528]. We investigate the asymptotic behavior of rank-width of a random graph G(n, p). We show that, asymptotically almost surely, (i 2 ), then rw(G(n, p)) =

Tree-width and circumference of graphs

✍ Etienne Birmele 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 37 KB

Coupled choosability of plane graphs

✍ Weifan Wang; Ko-Wei Lih 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

## Abstract A plane graph __G__ is coupled __k__‐choosable if, for any list assignment __L__ satisfying $|{{L}}({{x}})|= {{k}}$ for every ${{x}}\in {{V}}({{G}})\cup {{F}}({{G}})$, there is a coloring that assigns to each vertex and each face a color from its list such that any two adjacent or incid

Box-Rectangular Drawings of Plane Graphs

✍ Md.Saidur Rahman; Shin-ichi Nakano; Takao Nishizeki 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 413 KB

In this paper we introduce a new drawing style of a plane graph G called a box-rectangular drawing. It is defined to be a drawing of G on an integer grid such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal line segment or a vertical line segment, a

Every Graph Is an Integral Distance Grap

Every Graph Is an Integral Distance Graph in the Plane

✍ Hiroshi Maehara; Katsuhiro Ota; Norihide Tokushige 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 290 KB

We prove that every finite simple graph can be drawn in the plane so that any two vertices have an integral distance if and only if they are adjacent. The proof is constructive.

Simultaneously Colouring the Edges and F

Simultaneously Colouring the Edges and Faces of Plane Graphs

✍ Adrian O. Waller 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 345 KB

In a simultaneous colouring of the edges and faces of a plane graph we colour edges and faces so that every two adjacent or incident pair of them receive different colours. In this paper we prove a conjecture of Mel'nikov which states that for this colouring every plane graph can be coloured with 2+