Premium
On the chromaticity of certain subgraphs of a q‐tree
Author(s) -
Wanner Thomas
Publication year - 1989
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.3190130510
Subject(s) - combinatorics , mathematics , graph , chromatic polynomial , chromatic scale , chromaticity , discrete mathematics , computer science , artificial intelligence
Abstract We show that a graph G on n ⩾ q + 1 vertices (where q ⩾ 2) has the chromatic polynomial P(G;λ) = λ(λ − 1) … (λ − q + 2) (λ − q + 1) 2 (λ − q) n−q−1 if and only if G can be obtained from a q ‐tree T on n vertices by deleting an edge contained in exactly q − 1 triangles of T. Furthermore, we prove that these graphs are triangulated.