This work was inspired by new experimental findings where we discovered a two-dimensional (2D) material comprised of titanium-oxide-based one-dimensional (1D) sub-nanometer filaments. Preliminary results suggest that the 2D material contains considerable amounts of carbon, C, in addition to titanium, Ti, and oxygen, O. The aim of this study is to investigate the low-energy, stable atomic forms of 2D titanium carbo-oxides as a function of C content. Via a combination of first-principles calculations and an effective structure sampling scheme, the stable configurations of C-substitutions are comprehensively searched by templating different 2D TiO2 polymorphs and considering a two O to one C replacement scheme. Among the searched stable configurations, a structure where the (101) planes of anatase bound the top and bottom surfaces with a chemical formula of TiC1/4O3/2 was of particularly low energy. Furthermore, the variations in the electronic band structure and chemical bonding environments caused by the high-content C substitution are investigated via additional calculations using a hybrid exchange-correlation functional.