Determination of intra-tumor high-uptake area using 2-deoxy-2-[F-18]fluoro-d-glucose ([F-18]FDG) positron emission tomography (PET) imaging is an important consideration for dose painting in radiation treatment applications. The aim of our study was to develop a framework towards automated segmentation and labeling of homogeneous vs. heterogeneous tumors in clinical lung [F-18]FDG-PET with the capability of intra-tumor high-uptake region delineation. We utilized and extended a fuzzy random walk PET tumor segmentation algorithm to delineate intra-tumor high-uptake areas. Tumor textural feature (TF) analysis was used to find a relationship between tumor type and TF values. Segmentation accuracy was evaluated quantitatively utilizing 70 clinical [F-18]FDG-PET lung images of patients with a total of 150 solid tumors. For volumetric analysis, the Dice similarity coefficient (DSC) and Hausdorff distance (HD) measures were extracted with respect to gold-standard manual segmentation. A multi-linear regression model was also proposed for automated tumor labeling based on TFs, including cross-validation analysis. Two-tailed t test analysis of TFs between homogeneous and heterogeneous tumors revealed significant statistical difference for size-zone variability (SZV), intensity variability (IV), zone percentage (ZP), proposed parameters II and III, entropy and tumor volume (p < 0.001), dissimilarity, high intensity emphasis (HIE), and SUVmin (p < 0.01). Lower statistical differences were observed for proposed parameter I (p = 0.02), and no significant differences were observed for SUVmax and SUVmean. Furthermore, the Spearman rank analysis between visual tumor labeling and TF analysis depicted a significant correlation for SZV, IV, entropy, parameters II and III, and tumor volume (0.68 aerho ae0.84) and moderate correlation for ZP, HIE, homogeneity, dissimilarity, parameter I, and SUVmin (0.22 aerho ae0.52), while no correlations were observed for SUVmax and SUVmean (rho < 0.08). The multi-linear regression model for automated tumor labeling process resulted in R (2) and RMSE values of 0.93 and 0.14, respectively (p < 0.001), and generated tumor labeling sensitivity and specificity of 0.93 and 0.89. With respect to baseline random walk segmentation, the results showed significant (p < 0.001) mean DSC, HD, and SUVmean error improvements of 21.4 +/- 11.5 %, 1.4 +/- 0.8 mm, and 16.8 +/- 8.1 % in homogeneous tumors and 7.4 +/- 4.4 %, 1.5 +/- 0.6 mm, and 7.9 +/- 2.7 % in heterogeneous lesions. In addition, significant (p < 0.001) mean DSC, HD, and SUVmean error improvements were observed for tumor sub-volume delineations, namely 5 +/- 2 %, 1.5 +/- 0.6 mm, and 7 +/- 3 % for the proposed Fuzzy RW method compared to RW segmentation. We proposed and demonstrated an automatic framework for significantly improved segmentation and labeling of homogeneous vs. heterogeneous tumors in lung [F-18]FDG-PET images.