QP and QPS algorithms for software watermarking add extra edges to an interference graph of a program and then color the graph to embed a message by allocation of registers to variables. QP algorithm has a drawback that the embedded message is not always retrievable. QPS algorithm has a drawback that it can embed the shorter messages only. In this study, we present two new algorithms Color Change (CC) and Color Permutation (CP) that embed a message by changing the colors for the interference graph without changing its structure. CC algorithm is effective when the number of the variables in the program is large enough while CP algorithm is effective when the number of colors used in the interference graph is large enough. Both algorithms can retrieve any embedded messages and they can embed the longer messages into software.