无环图G的k顶点单射染色是指k种颜色1，2，...，k，对于图G的各点的一个分配，使得具有公共邻点的两点染以不同的颜色.G的单射色数是使得G为k单射可染的数k的最小值，记为xi(G)。　　单射染色起源于随机存取机的复杂性理论，可以应用到纠正错误编码的理论中.本文证明了确定一些特殊二部图的单射色数是NP-完全的，并证明了除非NP=ZPP，二部图的单射色数不会有n1/3-∈(∈>0)因子的近似.特别地，树图具有最优的单射染色算法。　　给定图G=(V，E)和权值函数ω：V→N，C1，C2，...，Ck为G的一个顶点单射k染色，该单射染色的权指的是每个色类中顶点最大权的和，即∑ki=1maxu∈Ciω(u).G的最大单射染色问题是指寻找G的某一单射染色C1，C2，...，Ck，使得它的权∑ki=1maxu∈Ciω(u)最小。　　本文证明了单射色数有界的幂弦图(power chordal graph)，有多项式时间完成的常因子的最大单射染色近似算法.进一步提出了多项式时间完成的算法MBFF，并证明它对于特殊二部图有常数的近似因子。　　对于图G，假定它的顶点是随着时间的推移一个接着一个给出的，并且每出现一个点，获得它和之前已出现的所有点在G内的导出子图.图G的在线单射染色算法就是指每出现一个点，该算法立即对其染色，使得有公共邻点的点不能染相同的颜色，并且不更改之前出现的点已染的颜色。　　本文证明了FF对于P3-free图来说，是一种多项式时间完成的、完美的在线单射染色算法，并得出FF*对于二部图是竞争比为3/2的在线单射染色算法.更进一步提出了多项式时间完成的在线算法BFF，该算法不仅提高了FF*的竞争比，而且是二部图的最优在线算法。