𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximal σ-polynomials of connected 3-chromatic graphs

✍ Scribed by Ioan Tomescu

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
113 KB
Volume
43
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 strict, where c~i~(G) denotes the number of i‐color partitions of G. In this paper the first ⌈ n/2 ⌉ levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003

📜 SIMILAR VOLUMES

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

## 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(

Classification of chromatically unique g
Classification of chromatically unique graphs having quadratic σ-polynomials
✍ Nian-Zu Li; Earl Glen Whitehead Jr.; Shao-Ji Xu 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 329 KB

Frucht and Giudici classified all graphs having quadratic a-polynomials. Here w e classify all chromatically unique graphs having quadratic (Tpolynomials.

The number of maximal independent sets i
The number of maximal independent sets in connected graphs
✍ Zoltán Füredi 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB 👁 1 views

Generalizing a theorem of Moon and Moser. we determine the maximum number of maximal independent sets in a connected graph on n vertices for n sufficiently large, e.g., n > 50. = I .32. . .). Example 1.2. Let b, = i(C,), where C,z denotes the circuit of length n. Then b, = 3, 6, = 2, b, = 5, and b,

Maximal K3's and Hamiltonicity of 4-conn
Maximal K3's and Hamiltonicity of 4-connected claw-free graphs
✍ Jun Fujisawa; Katsuhiro Ota 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB

## Abstract Let __cl__(__G__) denote Ryjáček's closure of a claw‐free graph __G__. In this article, we prove the following result. Let __G__ be a 4‐connected claw‐free graph. Assume that __G__[__N__~__G__~(__T__)] is cyclically 3‐connected if __T__ is a maximal __K__~3~ in __G__ which is also maxim