Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871909 | Discrete Applied Mathematics | 2016 | 9 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jihoon Choi, Kyeong Seok Kim, Suh-Ryung Kim, Jung Yeun Lee, Yoshio Sano,