Premium
Chromaticity of triangulated graphs
Author(s) -
Vaderlind Paul
Publication year - 1988
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.3190120215
Subject(s) - combinatorics , mathematics , chromaticity , chromatic polynomial , chromatic scale , graph , discrete mathematics , computer science , artificial intelligence
It is shown here that a connected graph G without subgraphs isomorphic to K 4 is triangulated if and only if its chromatic polynomial P ( G ,λ) equals λ(λ − 1) m (λ − 2) r for some integers m ≧ 1, r ≧ 0. This result generalizes the characterization of Two‐Trees given by E.G. Whitehead [“Chromaticity of Two‐Trees,” Journal of Graph Theory 9 (1985) 279–284].