On the partial order competition dimensions of chordal graphs

DOI10.1016/J.DAM.2016.08.020MaRDI QIDQ1786874zbMATH OpenOpenAlexFDO

Authors Jihoon Choi, Suh-Ryung Kim, Jung Yeun Lee, Yoshio Sano

Publication date 25 September 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.00204

zbMATH Keywords

\(d\)-partial ordercompetition graphpartial order competition dimensionblock graphchordal graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: 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}, emph{Discrete Applied Mathematics} (2015), exttt{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.

Recommendations

• The partial order competition dimensions of bipartite graphs
• On the competition graphs of \(d\)-partial orders
• The competition hypergraphs of doubly partial orders
• Cycle-free partial orders and chordal comparability graphs
• The \(m\)-step competition graphs of doubly partial orders

Cites work

• A class of acyclic digraphs with interval competition graphs
• Dimension-2 poset competition numbers and dimension-2 poset double competition numbers
• Distance-hereditary graphs
• On CCE graphs of doubly partial orders
• On the competition graphs of \(d\)-partial orders
• The \(m\)-step competition graphs of doubly partial orders
• The competition hypergraphs of doubly partial orders
• The niche graphs of doubly partial orders
• The phylogeny graphs of doubly partial orders
• Two minimal forbidden subgraphs for double competition graphs of posets of dimension at most two

Cited in

(4)

• On the competition graphs of \(d\)-partial orders
• A graph with the partial order competition dimension greater than five
• On the minimum clique partitioning problem on weighted chordal graphs
• The partial order competition dimensions of bipartite graphs

This page was built for publication: On the partial order competition dimensions of chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1786874)