For a graph G and a family of graphs F, the Turan number ex(G, F) is the maximum number of edges an F-free subgraph of G can have. We prove that ex(G, F) ≥ ex(Kr, F) if the chromatic number of G is r and F is a family of connected graphs. This result answers a question raised by Briggs and Cox ["Inverting the Turan problem', Discrete Math. 342(7) (2019), 1865-1884] about the inverse Turan number for all connected graphs.

被引：0

作者：

He, Zhen ^{[1
,2
]}

Lv, Zequn ^{[1
,2
]}

Zhu, Xiutao ^{[2
,3
]}

机构：

[1] Tsinghua Univ, Dept Math Sci, Beijing 100084, Peoples R China

[2] MTA Reny Inst, Budapest, Hungary

[3] Nanjing Univ, Dept Math, Nanjing 210093, Peoples R China

来源：

BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY | 2023年 / 108卷 / 02期

关键词：

inverse Turan problem; chromatic number; connected graph;

D O I：

10.1017/S0004972722001319

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For a graph G and a family of graphs , the Turan number is the maximum number of edges an -free subgraph of G can have. We prove that if the chromatic number of G is r and is a family of connected graphs. This result answers a question raised by Briggs and Cox ['Inverting the Turan problem', Discrete Math.342(7) (2019), 1865-1884] about the inverse Turan number for all connected graphs.

引用

页码：200 / 204

页数：5

共 12 条

[1] Bipartite subgraphs [J].

Alon, N .

COMBINATORICA, 1996, 16 (03) :301-311

[2] Inverting the Turan problem [J].

Briggs, Joseph ;

Cox, Christopher .

DISCRETE MATHEMATICS, 2019, 342 (07) :1865-1884

[3] Extremal C4-Free/C5-Free Planar Graphs [J].

Dowden, Chris .

JOURNAL OF GRAPH THEORY, 2016, 83 (03) :213-230

[4]

Erdos, 1946, STUD SCI MATH HUNG, V1, P51

[5] ON THE STRUCTURE OF LINEAR GRAPHS [J].

ERDOS, P ;

STONE, AH .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (12) :1087-1091

[6]

Erds P., 1984, GRAPH THEORY COMBINA, P1

[7] Star forests, dominating sets and Ramsey-type problems [J].

Ferneyhough, S ;

Haas, R ;

Hanson, D ;

MacGillivray, G .

DISCRETE MATHEMATICS, 2002, 245 (1-3) :255-262

[8] LARGE SUBGRAPHS WITHOUT SHORT CYCLES [J].

Foucaud, F. ;

Krivelevich, M. ;

Perarnau, G. .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (01) :65-78

[9] LARGE TRIANGLE-FREE SUBGRAPHS IN GRAPHS WITHOUT K4 [J].

FRANKL, P ;

RODL, V .

GRAPHS AND COMBINATORICS, 1986, 2 (02) :135-144

[10] Inverse Turan numbers [J].

Gyori, Ervin ;

Salia, Nika ;

Tompkins, Casey ;

Zamora, Oscar .

DISCRETE MATHEMATICS, 2022, 345 (05)

← 1 2 →