图着色（graph coloring），理学-计算机科学技术-计算机科学理论-离散数学-图论，各种颜色在图的顶点、边或者面上的分配。图着色理论是图论的一个重要分支，经典的图着色主要包括顶点着色、边着色和面着色。给定一个无向图，式中为顶点集合；为边集合，图的点着色问题就是将分为个颜色组，每个组形成一个独立集，即其中没有相邻的顶点；通俗地说就是用种颜色去染的顶点，使得有边相连的两个顶点染不同的颜色；也称这样的图是-点可染的。称使图是-点可染的最小为图的点色数，记为，一些显然的结果包括，，。布鲁克（Brooks）定理表明，如果是连通图，且不是完全图和奇圈，则，其中是的最大度。图的-着色判定问题（即给定无向连通图和种不同的颜色，判定是否有一种着色法使是-点可染的）又称着色问题，是最著名的NP-完全问题之一。给定一个无向图，其中为顶点集合；为边集合，图的边着色问题就是将分为个颜色组，每个组中没有相邻的两条边；通俗地说就是用种颜色去染的边，使得有公共顶点的两条边染不同的颜色；也称这样的图是-边可染的。称使图是-边可染的最小为图的边色数，记为。