The niche graphs of doubly partial orders

zbMATH Open1218.05061arXiv0905.3954MaRDI QIDQ3582500FDOQ3582500

Authors: Suh-Ryung Kim, Jung Yeun Lee, Boram Park, Won-Jin Park, Yoshio Sano 

Publication date: 2 September 2010

Abstract: The competition graph of a doubly partial order is known to be an interval graph. The competition-common enemy graph of a doubly partial order is also known to be an interval graph unless it contains a cycle of length 4 as an induced subgraph. In this paper, we show that the niche graph of a doubly partial order is not necessarily an interval graph. In fact, we prove that, for each integer n at least 4, there exists a doubly partial order whose niche graph contains an induced subgraph isomorphic to a cycle of length n. We also show that if the niche graph of a doubly partial order is triangle-free, then it is an interval graph.

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

Recommendations

• The niche graphs of interval orders
• The phylogeny graphs of doubly partial orders
• scientific article; zbMATH DE number 15868
• On CCE graphs of doubly partial orders
• On the partial order polytope of a digraph
• The competition hypergraphs of doubly partial orders
• Then-ordered graphs: A new graph class
• scientific article; zbMATH DE number 4033799
• Some recent results on niche graphs
• On the competition graphs of \(d\)-partial orders

zbMATH Keywords

interval graphniche graphdoubly partial order

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Cited In (10)

• On the partial order competition dimensions of chordal graphs
• The niche graphs of interval orders
• On the competition graphs of \(d\)-partial orders
• A graph with the partial order competition dimension greater than five
• On CCE graphs of doubly partial orders
• The phylogeny graphs of doubly partial orders
• The \(m\)-step competition graphs of doubly partial orders
• The competition hypergraphs of doubly partial orders
• Niche hypergraphs
• The partial order competition dimensions of bipartite graphs

This page was built for publication: The niche graphs of doubly partial orders

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