A novel adaptive graph traversal-based steganographic scheme for pale tte images is proposed.Each color in the palette is considered to be a graph node,and a colo r-graph is constructed by exploiting the difference of luminance and Euclid distance betwee n any two colors. Assignment of secret bit for each color-node is completed according to traversa l of a graph. During the data embedding,the adaptive rule is built by exploiting correlations among colors of the pixels.Comparative experimental results show that the proposed scheme can g ain a larger capacity,maintain quite good image quality,and be more resistant to HCF-attack,compared with some other steganographic schemes.