Directed Intersection Representations and the Information Content of Digraphs

Xujun Liu*, Roberto Assis Machado, Olgica Milenkovic

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Consider a directed graph (digraph) in which vertices are assigned color sets, and two vertices are connected if and only if they share at least one color and the tail vertex has a strictly smaller color set than the head. We seek to determine the smallest possible size of the union of the color sets that allows for such a digraph representation. To address this problem, we introduce the new notion of a directed intersection representation of a digraph, and show that it is well-defined for all directed acyclic graphs (DAGs). We then proceed to introduce the directed intersection number (DIN), the smallest number of colors needed to represent a DAG. Our main results are upper bounds on the DIN of DAGs based on what we call the longest terminal path decomposition of the vertex set, and constructive lower bounds.

Original languageEnglish
Article number9236641
Pages (from-to)347-357
Number of pages11
JournalIEEE Transactions on Information Theory
Issue number1
Publication statusPublished - Jan 2021
Externally publishedYes


  • Directed intersection number
  • directed acyclic graph
  • intersection representation


Dive into the research topics of 'Directed Intersection Representations and the Information Content of Digraphs'. Together they form a unique fingerprint.

Cite this