The Phylogeny Graphs of Doubly Partial Orders
Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 4, p. 657.

Voir la notice de l'article dans European Digital Mathematics Library

The competition graph of a doubly partial order is known to be an interval graph. The CCE graph and the niche graph of a doubly partial order are also known to be interval graphs if the graphs do not contain a cycle of length four and three as an induced subgraph, respectively. Phylogeny graphs are variant of competition graphs. The phylogeny graph P(D) of a digraph D is the (simple undirected) graph defined by V (P(D)) := V (D) and E(P(D)) := {xy | N+D (x) ∩ N+D(y) ¹ ⊘ } ⋃ {xy | (x,y) ∈ A(D)}, where N+D(x):= {v ∈ V(D) | (x,v) ∈ A (D)}. In this note, we show that the phylogeny graph of a doubly partial order is an interval graph. We also show that, for any interval graph G̃, there exists an interval graph G such that G̃ contains the graph G as an induced subgraph and that G̃ is the phylogeny graph of a doubly partial order.
Classification : 92D15, 05C20, 05C75
Mots-clés : competition graph, phylogeny graph, doubly partial order, interval graph 
@article{DMGT_2013__33_4_267778,
     author = {Boram Park and Yoshio Sano},
     title = {The {Phylogeny} {Graphs} of {Doubly} {Partial} {Orders}},
     journal = {Discussiones Mathematicae Graph Theory},
     pages = {657},
     publisher = {mathdoc},
     volume = {33},
     number = {4},
     year = {2013},
     zbl = {1295.05117},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_4_267778/}
}
TY  - JOUR
AU  - Boram Park
AU  - Yoshio Sano
TI  - The Phylogeny Graphs of Doubly Partial Orders
JO  - Discussiones Mathematicae Graph Theory
PY  - 2013
SP  - 657
VL  - 33
IS  - 4
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_4_267778/
LA  - en
ID  - DMGT_2013__33_4_267778
ER  - 
%0 Journal Article
%A Boram Park
%A Yoshio Sano
%T The Phylogeny Graphs of Doubly Partial Orders
%J Discussiones Mathematicae Graph Theory
%D 2013
%P 657
%V 33
%N 4
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_4_267778/
%G en
%F DMGT_2013__33_4_267778
Boram Park; Yoshio Sano. The Phylogeny Graphs of Doubly Partial Orders. Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 4, p. 657. https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_4_267778/