Connected triangle-free m-step competition graphs

AbstractIn 1968, Cohen presented competition graphs in connection with the study of ecological systems. Recently, Cho, Kim and Nam introduced a generalization called the m-step competition graph. In this paper, we characterize connected triangle-free m-step competition graphs on n vertices for m⩾n. The analogous result follows for same-step competition graphs. We also demonstrate that the path on n vertices is an (n-1)-step and an (n-2)-step competition graph. Finally, we resolve a question of Cho, Kim and Nam on an inequality between 1-step and m-step competition numbers