We have performed electronic structure calculations of the interaction of potassium and oxygen with graphite (GR), individually and as coadsorbates. We use up to three graphite planes to represent the graphite surface, but we show that the main physics is correctly described by a single graphite layer. At low coverage the potassium-graphite bond is largely ionic, and the variation of the K-GR bond energy with the lateral position of the K atom in the graphite unit cell is very small. We study the interaction between atomic oxygen and graphite, We find that O binds strongest at the bridge site, but the barrier for diffusion is rather small. The frequency for the perpendicular O-graphite vibrational mode is remarkably low (53 meV), reflecting the relative slow variation of the O-graphite interaction energy with the separation z between the O atom and the graphite surface. We consider the adsorption of O-2 on a clean graphite surface and on a graphite surface with a low concentration of potassium. On the clean surface the O-2-graphite interaction is found to be repulsive (the weak attractive van der Waals interaction is not included in our theoretical method), in accordance with the extremely low sticking coefficient observed for O-2 on clean graphite. When potassium is adsorbed on the graphite surface, O-2 chemisorbs at the potassium sites which is consistent with the large sticking coefficient observed for O-2 On a potassium covered surface. The energy barrier towards dissociation of O-2 On the clean graphite surface is estimated to be similar to that of gas phase O-2 For O-2 on K/graphite we find that O-2 chemisorbs "side-on" K, and that the barrier for dissociation is much smaller than in the gas phase or on the clean graphite surface.