This study aimed to develop software for tumor segmentation on 18F-fluorodeoxyglucose (FDG) positron emission tomography (PET). To segment the tumor from the background, we used graph cut, whose segmentation energy was generally divided into two terms: the unary and pairwise terms. Locally connected conditional random fields (LCRF) was proposed for the pairwise term. In LCRF, a three-dimensional cubic window with length L was set for each voxel, and voxels within the window were considered for the pairwise term. To evaluate our method, 64 clinically suspected metastatic bone tumors were tested, which were revealed by FDG-PET. To obtain ground truth, the tumors were manually delineated via consensus of two board-certified radiologists. To compare the LCRF accuracy, other types of segmentation were also applied such as region-growing based on 35%, 40%, and 45% of the tumor maximum standardized uptake value (RG35, RG40, and RG45, respectively), SLIC superpixels (SS), and region-based active contour models (AC). To validate the tumor segmentation accuracy, a dice similarity coefficient (DSC) was calculated between manual segmentation and result of each technique. The DSC difference was tested using the Wilcoxon signed rank test. The mean DSCs of LCRF at L = 3, 5, 7, and 9 were 0.784, 0.801, 0.809, and 0.812, respectively. The mean DSCs of other techniques were RG35, 0.633; RG40, 0.675; RG45, 0.689; SS, 0.709; and AC, 0.758. The DSC differences between LCRF and other techniques were statistically significant (p <0.05). In conclusion, tumor segmentation was more reliably performed with LCRF relative to other techniques.