𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Quasi-planar graphs have a linear number of edges

✍ Scribed by Pankaj K. Agarwal; Boris Aronov; János Pach; Richard Pollack; Micha Sharir

Publisher
Springer-Verlag
Year
1997
Tongue
English
Weight
467 KB
Volume
17
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Edge-partitions of planar graphs and the
Edge-partitions of planar graphs and their game coloring numbers
✍ Wenjie He; Xiaoling Hou; Ko-Wei Lih; Jiating Shao; Weifan Wang; Xuding Zhu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB 👁 1 views

Let G be a planar graph and let g(G) and Á(G) be its girth and maximum degree, respectively. We show that G has an edge-partition into a forest and a subgraph H so that (i) -cycles (though it may contain 3-cycles). These results are applied to find the following upper bounds for the game coloring n

The number of edge 3-colorings of a plan
The number of edge 3-colorings of a planar cubic graph as a permanent
✍ David E. Scheim 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 370 KB

In this paper, we establish that the number of edge 3-colorings of a finite planar cubic graph G, i.e., 3-colorings of its interchange graph H, is equal to 2\*lPermanent(A)l, where N is the number of edges of G, and A is the 2N X 2iV square matrix formed by repeating each row of the N X 2N vertexdir