✦ LIBER ✦

Maximum chromatic polynomials of 2-connected graphs

✍ Scribed by Ioan Tomescu

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 345 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180404

No coin nor oath required. For personal study only.

✦ Synopsis

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(G; λ): G is 2‐connected of order n and G ≠ C~n~} and all extremal graphs relative to this property, with some consequences on the maximum number of 3‐colorings in the class of 2‐connected graphs of order n having ~X~(G) = 2 and ~X~(G) = 3, respectively. For every n ≧ 5 and λ ≧ 4, the first three maximum chromatic polynomials of 2‐connected graphs are determined.

📜 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

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

Characterization of maximum critically 2

Characterization of maximum critically 2-connected graphs

✍ R. C. Entringer 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 346 KB

## Abstract A graph __G__ is critically 2‐connected if __G__ is 2‐connected but, for any point __p__ of __G, G — p__ is not 2‐connected. Critically 2‐connected graphs on __n__ points that have the maximum number of lines are characterized and shown to be unique for __n__ ⩾ 3, __n__ ≠ 11.

Circular chromatic index of graphs of ma

Circular chromatic index of graphs of maximum degree 3

✍ Peyman Afshani; Mahsa Ghandehari; Mahya Ghandehari; Hamed Hatami; Ruzbeh Tusserk 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

## Abstract This paper proves that if __G__ is a graph (parallel edges allowed) of maximum degree 3, then χ′~__c__~(__G__) ≤ 11/3 provided that __G__ does not contain __H__~1~ or __H__~2~ as a subgraph, where __H__~1~ and __H__~2~ are obtained by subdividing one edge of __K__ (the graph with three

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 👁 1 views

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

Total chromatic number of planar graphs

Total chromatic number of planar graphs with maximum degree ten

✍ Weifan Wang 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB 👁 1 views