Inducibility of directed paths
Date
2020-10
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Abstract
A long standing open problem in extremal graph theory is to describe all graphs that maximize the number of induced copies of a path on four vertices. The character of the problem
changes in the setting of oriented graphs, and becomes more tractable. Here we resolve this problem in the setting of oriented graphs without transitive triangles.
Series Number
Journal Issue
Is Version Of
Versions
Article
Inducibility of directed paths
(
2018-11-09)
A long standing open problem in extremal graph theory is to describe all graphs that maximize the number of induced copies of a path on four vertices. The character of the problem changes in the setting of oriented graphs, and becomes more tractable. Here we resolve this problem in the setting of oriented graphs without transitive triangles.
Series
Academic or Administrative Unit
Type
Article
Comments
This is a manuscript of an article published as Choi, Ilkyoo, Bernard Lidický, and Florian Pfender. "Inducibility of directed paths." Discrete Mathematics 343, no. 10 (2020): 112015. doi:10.1016/j.disc.2020.112015.
Rights Statement
This manuscript is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.