✦ LIBER ✦

Chromaticity of series-parallel graphs

✍ Scribed by K.M. Koh; C.P. Teo

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 454 KB
Volume: 154
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00355-m

No coin nor oath required. For personal study only.

✦ Synopsis

By applying a sequence of edge-gluings on a set of cycles each of length k, we obtain a special series-parallel graph. The well-known k-gon tree theorem (see [l, lo]) states that these graphs form a X-equivalence class. Many of the other known classes of X-unique graphs and X-equivalence classes are also special cases of series-parallel graphs. This paper introduces some new chromatic invariants for this class of graphs. We illustrate the usefulness of these invariants by constructing several new X-equivalence classes which include edge-gluings of graphs in a special class of series-parallel graphs. The latter result parallels that of the k-gon tree theorem.

📜 SIMILAR VOLUMES

The circular chromatic number of series-

The circular chromatic number of series-parallel graphs

✍ Hell, Pavol; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB 👁 2 views

In this article, we consider the circular chromatic number χ c (G) of series-parallel graphs G. It is well known that series-parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a seriesparallel graph G contains a triangle, then both the chromati

Density of the circular chromatic number

Density of the circular chromatic numbers of series-parallel graphs

✍ Zhishi Pan; Xuding Zhu 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 1 views

## Abstract Suppose __G__ is a series‐parallel graph. It was proved in 3 that either ~χ__c__~(__G__) = 3 or ~χ__c__~(__G__) ≤ 8/3. So none of the rationals in the interval (8/3, 3) is the circular chromatic number of a series‐parallel graph. This paper proves that for every rational __r__ ∈ [2, 8/3

The circular chromatic number of series-

The circular chromatic number of series-parallel graphs with large girth

✍ Chien, Chihyun; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It was proved by Hell and Zhu that, if G is a series-parallel graph of girth at least 2 (3k -1)/2 , then χ c (G) ≤ 4k/(2k -1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series-parallel graph G of girth 2 (3k -1)/2 -1 such that χ c (G) > 4k/(2k -1)

Chromaticity of triangulated graphs

✍ Paul Vaderlind 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

A graph G is called triangulated (or rigid-circuit graph, or chordal graph) if every circuit of G with length greater than 3 has a chord. It can be shown (see, UI, . . . , u,, . Let G = G,.

Colouring series-parallel graphs

✍ P. D. Seymour 📂 Article 📅 1990 🏛 Springer-Verlag 🌐 English ⚖ 634 KB

Equistable series–parallel graphs

✍ Ephraim Korach; Uri N. Peled 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 163 KB

A graph is called equistable when there is a non-negative weight function on its vertices such that a set S of vertices has total weight 1 if and only if S is maximal stable. We characterize those series-parallel graphs that are equistable, generalizing results of Mahadev et al. about equistable out