2015/05/01 by Jihoon Choi, Suh-Ryung Kim, Choi, Jihoon +5 · 1 citation
Computer Science · Mathematics · #05C20 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems #math.CO #msc:05C20 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1505.00204
13 pages, 4 figures
openalex publication_date 2015/05/01 · arxiv created 2016/01/08 · arxiv updated 2016/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Choi \it et al. [J.~Choi, K.~S.~Kim, S.~-R.~Kim, J.~Y.~Lee, and Y.~Sano: On the competition graphs of d-partial orders, Discrete Applied Mathematics (2015), http://dx.doi.org/10.1016/j.dam.2015.11.004] introduced the notion of the partial order competition dimension of a graph. It was shown that complete graphs, interval graphs, and trees, which are chordal graphs, have partial order competition dimensions at most three. In this paper, we study the partial order competition dimensions of chordal graphs. We show that chordal graphs have partial order competition dimensions at most three if the graphs are diamond-free. Moreover, we also show the existence of chordal graphs containing diamonds whose partial order competition dimensions are greater than three.