On the partial order competition dimensions of chordal graphs

DOI10.1016/J.DAM.2016.08.020zbMATH Open1396.05044arXiv1505.00204OpenAlexW2963506471MaRDI QIDQ1786874FDOQ1786874

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)

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.

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

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

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)

Cites Work

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

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)