Inducibility of directed paths

被引：7
作者：
Choi, Ilkyoo [1 ]
Lidicky, Bernard [2 ]
Pfender, Florian [3 ]
机构：
[1] Hankuk Univ Foreign Studies, Dept Math, Yongin, Gyeonggi Do, South Korea
[2] Iowa State Univ, Dept Math, Ames, IA USA
[3] Univ Colorado, Dept Math & Stat Sci, Denver, CO 80202 USA
来源：
DISCRETE MATHEMATICS | 2020年 / 343卷 / 10期
基金：
新加坡国家研究基金会;
关键词：
Induced subgraph; Inducibility; Directed path; MAXIMUM NUMBER; TRIANGLES; PENTAGONS; DENSITY;
D O I：
10.1016/j.disc.2020.112015
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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. (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页数：11
相关论文
共 35 条
  • [1] Aroskar A., 2014, J SYMB LOGIC
  • [2] A SOLUTION TO THE 2/3 CONJECTURE
    Baber, Rahil
    Talbot, John
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014, 28 (02) : 756 - 766
  • [3] Hypergraphs Do Jump
    Baber, Rahil
    Talbot, John
    [J]. COMBINATORICS PROBABILITY & COMPUTING, 2011, 20 (02) : 161 - 171
  • [4] Rainbow triangles in three-colored graphs
    Balogh, Jozsef
    Hu, Ping
    Lidicky, Bernard
    Pfender, Florian
    Volec, Jan
    Young, Michael
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 126 : 83 - 113
  • [5] Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
    Balogh, Jozsef
    Hu, Ping
    Lidicky, Bernard
    Pfender, Florian
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2016, 52 : 47 - 58
  • [6] Minimum Number of Monotone Subsequences of Length 4 in Permutations
    Balogh, Jozsef
    Hu, Ping
    Lidicky, Bernard
    Pikhurko, Oleg
    Udvari, Balazs
    Volec, Jan
    [J]. COMBINATORICS PROBABILITY & COMPUTING, 2015, 24 (04) : 658 - 679
  • [7] Upper bounds on the size of 4-and 6-cycle-free subgraphs of the hypercube
    Balogh, Jozsef
    Hu, Ping
    Lidicky, Bernard
    Liu, Hong
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2014, 35 : 75 - 85
  • [8] Coregliano L.N., 2015, PREPRINT
  • [9] On the Density of Transitive Tournaments
    Coregliano, Leonardo Nagami
    Razborov, Alexander A.
    [J]. JOURNAL OF GRAPH THEORY, 2017, 85 (01) : 12 - 21
  • [10] Monochromatic triangles in three-coloured graphs
    Cummings, James
    Kral, Daniel
    Pfender, Florian
    Sperfeld, Konrad
    Treglown, Andrew
    Young, Michael
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (04) : 489 - 503
1234