✦ LIBER ✦

Maximum chromatic polynomial of 3-chromatic blocks

✍ Scribed by Ioan Tomescu

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 397 KB
Volume: 172
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00276-2

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper it is proved that if the chromatic polynomial P(G; 2) is maximum for 2 = 3 in the class of 3-chromatic 2-connected graphs G of order n, then G is isomorphic to the graph consisting of C4 and Cn-l, having in common a path of length two for every even n/> 6. This solves a conjecture raised in (Tomescu, 1994). Also, the fourth maximum chromatic polynomial P(G; 2) for 2 = 3 in the class of 2-connected graphs of order n and all extremal graphs are deduced for every n >~ 5.

📜 SIMILAR VOLUMES

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(

Expansions of the chromatic polynomial

✍ Norman Biggs 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 739 KB

The chromatic polynomial ;X chromial) of a graph was first defined by Birkhoff in 1912, ;md gives the number of ways or" properly colov iing the vertices of the graph with any number of colours. A good survey of the b-sic facts about these polynomials may be found in the article by Read [ 3 3 . It

Chromatic polynomials of hypergraphs

✍ Ewa Drgas-Burchardt; Ewa Łazuka 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 182 KB

We consider a natural generalization of the chromatic polynomial of a graph. Let the symbol f (x 1 ,...,x m ) (H, λ) denote a number of different λ-colourings of a hypergraph H = (X, E), where X = {v 1 , . . . , v n } and E = {e 1 , . . . , e m }, satisfying that in an edge e i there are used at lea

Coefficients of chromatic polynomials

✍ G.H.J Meredith 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 129 KB

Proof of a Chromatic Polynomial Conjectu

Proof of a Chromatic Polynomial Conjecture

✍ F.M. Dong 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 138 KB

Let P(G, \*) denote the chromatic polynomial of a graph G. It is proved in this paper that for every connected graph G of order n and real number \* n, (\*&2) n&1 P(G, \*)&\*(\*&1) n&2 P(G, \*&1) 0. By this result, the following conjecture proposed by Bartels and Welsh is proved: P(G, n)(P(G, n&1))

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