Article ID Journal Published Year Pages File Type
6871909 Discrete Applied Mathematics 2016 9 Pages PDF
Abstract
In this paper, we study the competition graphs of d-partial orders and obtain their characterization which extends results given by Cho and Kim (2005). We also show that any graph can be made into the competition graph of a d-partial order for some positive integer d as long as adding isolated vertices is allowed. We then study graphs whose partial order competition dimensions are at most three, where the partial order competition dimension of a graph G is the smallest nonnegative integer d such that G together with some isolated vertices is the competition graph of a d-partial order.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , ,