I've been following the red to soot black path as well, and I did end up in the Regal Purple. From there, I tried to use pears, but instead of getting Gloom Purple, I found myself with a Mole Brown chocobo! Again, I tried pears, and what do you know, I find myself with another color missing on the chart, Olive Green. Now way off the map, I decided to try apples, but it brought my chocobo back to Mole Brown. Just in case someone wanted to know how to get either of those colors, although I'm not sure if there's other ways possible. Still trying to get from Mole Brown to Soot Black though, if anyone has any advice, please let me know!