Premium
Graphs with least number of colorings
Author(s) -
Sakaloglu A.,
Satyanarayana A.
Publication year - 1995
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.3190190407
Subject(s) - combinatorics , mathematics , graph , edge coloring , planar graph , 1 planar graph , chordal graph , discrete mathematics , graph coloring , graph power , line graph
A λ‐coloring of a graph G is an assignment of λ or fewer colors to the points of G so that no two adjacent points have the same color. Let Ω (n,e) be the collection of all connected n‐point and e‐edge graphs and let Ωp(n,e) be the planar graphs of Ω(n, e). This paper characterizes the graphs that minimize the number of λ‐colorings in Ω(n, e) for all λ > 1 and Ωp(n,e) for all λ.4. © 1995 John Wiley & Sons, Inc.