Accurate lung tumor delineation plays an important role in radiotherapy treatment planning. Since the lung tumor has poor boundary in positron emission tomography (PET) images and low contrast in computed tomography (CT) images, segmentation of tumor in the PET and CT images is a challenging task. In this paper, we effectively integrate the two modalities by making fully use of the superior contrast of PET images and superior spatial resolution of CT images. Random walk and graph cut method is integrated to solve the segmentation problem, in which random walk is utilized as an initialization tool to provide object seeds for graph cut segmentation on the PET and CT images. The co-segmentation problem is formulated as an energy minimization problem which is solved by max-flow/min-cut method. A graph, including two sub-graphs and a special link, is constructed, in which one sub-graph is for the PET and another is for CT, and the special link encodes a context term which penalizes the difference of the tumor segmentation on the two modalities. To fully utilize the characteristics of PET and CT images, a novel energy representation is devised. For the PET, a downhill cost and a 3D derivative cost are proposed. For the CT, a shape penalty cost is integrated into the energy function which helps to constrain the tumor region during the segmentation. We validate our algorithm on a data set which consists of 18 PET-CT images. The experimental results indicate that the proposed method is superior to the graph cut method solely using the PET or CT is more accurate compared with the random walk method, random walk co-segmentation method, and non-improved graph cut method.