✦ LIBER ✦

A characterization of ?-outerplanar graphs

✍ Scribed by Wargo, Lawrence

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 528 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199609)23:1<57::aid-jgt7>3.0.co;2-j

No coin nor oath required. For personal study only.

✦ Synopsis

Chartrand and Harary have shown that if G is a non-outerplanar graph such that, for every edge e, both the deletion G \ e and the contraction G/e of e from G are outerplanar, then G is isomorphic to K4 or K2,3. An a-outerplanar graph is a graph which is not outerplanar such that, for some edge a , both G \ a and G / a are outerplanar. We describe various results for the class of a-outerplanar graphs and obtain a characterization of the class.

📜 SIMILAR VOLUMES

Pathwidth of outerplanar graphs

✍ David Coudert; Florian Huc; Jean-Sébastien Sereni 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

## Abstract We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geo

Centers of maximal outerplanar graphs

✍ Andrzej Proskurowski 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 178 KB

## Abstract The center of a graph is defined to be the subgraph induced by the set of vertices that have minimum eccentricities (i.e., minimum distance to the most distant vertices). It is shown that only seven graphs can be centers of maximal outerplanar graphs.

Outerplanar Partitions of Planar Graphs

✍ Kiran S. Kedlaya 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 254 KB

An outerplanar graph is one that can be embedded in the plane so that all of the vertices lie on one of the faces. We investigate a conjecture of Chartrand, Geller, and Hedetniemi, that every planar graph can be edge-partitioned into two outerplanar subgraphs. We refute the stronger statement that e

Game chromatic number of outerplanar gra

Game chromatic number of outerplanar graphs

✍ Guan, D. J.; Zhu, Xuding 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 2 views

This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs.

Acyclic edge chromatic number of outerpl

Acyclic edge chromatic number of outerplanar graphs

✍ Jian-Feng Hou; Jian-Liang Wu; Gui-Zhen Liu; Bin Liu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB

## Abstract A proper edge coloring of a graph __G__ is called acyclic if there is no 2‐colored cycle in __G__. The acyclic edge chromatic number of __G__, denoted by χ(__G__), is the least number of colors in an acyclic edge coloring of __G__. In this paper, we determine completely the acyclic edge

The relaxed game chromatic number of out

The relaxed game chromatic number of outerplanar graphs

✍ Charles Dunn; Hal A. Kierstead 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

## Abstract The (__r__,__d__)‐relaxed coloring game is played by two players, Alice and Bob, on a graph __G__ with a set of __r__ colors. The players take turns coloring uncolored vertices with legal colors. A color α is legal for an uncolored vertex __u__ if __u__ is adjacent to at most __d__ vert