Puzzling and apuzzling graphs

Abstract

Let G be a graph with chromatic number χ(G) and consider a partition P of G into connected subgraphs. P is a puzzle on G if there is a unique vertex coloring of G using 1, 2, …, χ(G) such that the sums of the numbers assigned to the partition pieces are all the same. P is an apuzzle if there is a unique vertex coloring such that the sums are all different. We investigate the concept of puzzling and apuzzling graphs, detailing classes of graphs that are puzzling, apuzzling and neither.

Keywords

• Vertex coloring
• Puzzles
• Partitions