𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Chromatic polynomials, polygon trees, and outerplanar graphs

✍ Scribed by C. D. Wakelin; D. R. Woodall

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
370 KB
Volume
16
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

It is proved that all classes of polygon trees are characterized by their chromatic polynomials, and a characterization is given of those polynominals that are chromatic polynomials of outerplanar graphs. The first result yields an alternative proof that outerplanar graphs are recognizable from their vertex‐deleted subgraphs. © 1929 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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

Maximal chromatic polynomials of connect
Maximal chromatic polynomials of connected planar graphs
✍ Ioan Tomescu 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 429 KB 👁 1 views

## Abstract In this paper we obtain chromatic polynomials of connected 3‐ and 4‐chromatic planar graphs that are maximal for positive integer‐valued arguments. We also characterize the class of connected 3‐chromatic graphs having the maximum number of __p__‐colorings for __p__ ≥ 3, thus extending a

Maximum chromatic polynomials of 2-conne
Maximum chromatic polynomials of 2-connected graphs
✍ Ioan Tomescu 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 345 KB 👁 1 views

## Abstract In this paper we obtain chromatic polynomials __P(G__; λ) of 2‐connected graphs of order __n__ that are maximum for positive integer‐valued arguments λ ≧ 3. The extremal graphs are cycles __C__~__n__~ and these graphs are unique for every λ ≧ 3 and __n__ ≠ 5. We also determine max{__P(

Maximal σ-polynomials of connected 3-chr
Maximal σ-polynomials of connected 3-chromatic graphs
✍ Ioan Tomescu 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 113 KB 👁 1 views

## Abstract In the set of graphs of order __n__ and chromatic number __k__ the following partial order relation is defined. One says that a graph __G__ is less than a graph __H__ if __c__~__i__~(__G__) ≤ __c__~__i__~(__H__) holds for every __i__, __k__ ≤ __i__ ≤ __n__ and at least one inequality is