Premium
Maximum chromatic polynomials of 2‐connected graphs
Author(s) -
Tomescu Ioan
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180404
Subject(s) - combinatorics , mathematics , chromatic scale , integer (computer science) , order (exchange) , discrete mathematics , class (philosophy) , chordal graph , indifference graph , graph , computer science , finance , economics , programming language , artificial intelligence
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.