The -step competition graphs of doubly partial orders

Abstract: The competition graph of a doubly partial order is an interval graph. The competition-common enemy graph, a variant of the competition graph, of a doubly partial order is also an interval graph if it does not contain a 4-cycle as an induced subgraph. It is natural to ask whether or not the same phenomenon occurs for other interesting variants of the competition graph. In this paper, we study the -step competition graph, a generalization of the competition graph, of a doubly partial order. We show that the -step competition graph of a doubly partial order is an interval graph for every positive integer . We also show that given a positive integer , an interval graph with sufficiently many isolated vertices is the -step competition graph of a doubly partial order. [Copyright &y& Elsevier]