We present maps of ^ { 12 } \text { CO } ~ { } J = 2 - 1 emission covering the entire star-forming disks of 16 nearby dwarf galaxies observed by the IRAM HERACLES survey . The data have 13″ angular resolution , \sim 250  pc at our average distance of D = 4  Mpc , and sample the galaxies by 10 - 1000 resolution elements . We apply stacking techniques to perform the first sensitive search for CO emission in dwarf galaxies outside the Local Group ranging from individual lines-of-sight , stacking over IR-bright regions of embedded star formation , and stacking over the entire galaxy . We detect 5 galaxies in CO with total CO luminosities of L _ { CO 2 - 1 } = 3 - 28 \times 10 ^ { 6 } K km s ^ { -1 }  pc ^ { 2 } . The other 11 galaxies remain undetected in CO even in the stacked images and have L _ { CO 2 - 1 } \lesssim 0.4 - 8 \times 10 ^ { 6 } K km s ^ { -1 }  pc ^ { 2 } . We combine our sample of dwarf galaxies with a large sample of spiral galaxies from the literature to study scaling relations of L _ { CO } with M _ { B } and metallicity . We find that dwarf galaxies with metallicities of Z \approx 1 / 2 - 1 / 10 ~ { } Z _ { \odot } have L _ { CO } of 2 - 4 orders of magnitude smaller than massive spiral galaxies and that their L _ { CO } per unit L _ { B } is 1 - 2 orders of magnitude smaller . A comparison with tracers of star formation ( FUV and 24µm ) shows that L _ { CO } per unit SFR is 1 - 2 orders of magnitude smaller in dwarf galaxies . One possible interpretation is that dwarf galaxies form stars much more efficiently , we argue that the low L _ { CO } / \text { SFR } ratio is due to the fact that the CO-to-H _ { 2 } conversion factor , \alpha _ { CO } , changes significantly in low metallicity environments . Assuming that a constant H _ { 2 } depletion time of \tau _ { dep } = 1.8  Gyr holds in dwarf galaxies ( as found for a large sample of nearby spirals ) implies \alpha _ { CO } values for dwarf galaxies with Z \approx 1 / 2 - 1 / 10 ~ { } Z _ { \odot } that are more than one order of magnitude higher than those found in solar metallicity spiral galaxies . Such a significant increase of \alpha _ { CO } at low metallicity is consistent with previous studies , in particular those of Local Group dwarf galaxies which model dust emission to constrain H _ { 2 } masses . Even though it is difficult to parameterize the dependence of \alpha _ { CO } on metallicity given the currently available data the results suggest that CO is increasingly difficult to detect at lower metallicities . This has direct consequences for the detectability of star-forming galaxies at high redshift which presumably have on average sub-solar metallicity .