基于图着色的分配算法是将调度结果转化为图模型，再利用图论中的图着色算法来求解分配问题。这种算法每次只进行一种行为实体（例如操作）的分配。
基于图着色的分配算法使用的图模型称为冲突图（conflict graph）。冲突图由二元式组成：
G = { V, E}
其中 V = { vi | 调度结果中的操作i}
E = {( vi, vj )| 操作i与操作j非互斥且被调度到同一控制步中}
或
V = { vi | 调度结果中的变量i}
E = {( vi, vj )| 变量i与变量j非互斥且其生存周期交叠}
冲突图中的结点代表操作（或变量），边代表操作（或变量）之间存在冲突（不能共享硬件资源）。
通过下述实例有助于理解基于图着色算法的分配算法。
现在以实例说明冲突图和图着色算法。图5.18是题目diffeq的一个调度结果，为了阅读方便将其复制到图5.28(a)，其相应的冲突图示于图5.28(b)。冲突图中的结点代表操作，有边相连的结点不能共享硬件资源。例如，操作1，3，4被调度到同一控制步中，他们不是互斥操作，因而不能共享硬件资源，所以结点1，3，4之间有边相连。操作1和操作2不在同一控制步中，可以共享硬件资源，因而结点1和结点2之间没有边相连。
图5.28 与调度结果对应的冲突图 .gif)
.gif) |
图着色算法是对冲突图中所有结点进行着色，任何冲突结点不得具有相同颜色。将图着色算法用于分配问题，则是不同颜色的结点不得共享硬件资源。着色算法的过程如下：
(1) 在冲突图中任意选取一个尚未着色的结点；
(2) 对被选取的结点着以与其相邻（有边和其相连）已着色结点不同的颜色；
(3) 重复上述步骤，直至所有结点均已着色。