Counting Gallai 3-colorings of complete graphs

被引：3

作者：

Bastos, Josefran de Oliveira ^{[1
]}

Benevides, Fabricio Siqueira ^{[2
]}

Mota, Guilherme Oliveira ^{[3
]}

Sau, Ignasi ^{[4
]}

机构：

[1] Univ Fed Ceara, Engn Comp, Fortaleza, Ceara, Brazil

[2] Univ Fed Ceara, Dept Matemat, Fortaleza, Ceara, Brazil

[3] Univ Fed ABC, Ctr Matemat Comp & Cognicao, Santo Andre, Brazil

[4] Univ Montpellier, CNRS, LIRMM, Montpellier, France

来源：

DISCRETE MATHEMATICS | 2019年 / 342卷 / 09期

基金：

巴西圣保罗研究基金会;

关键词：

Gallai colorings; Rainbow triangles; Complete graphs; Counting; EDGE-COLORINGS; NUMBER; SETS;

D O I：

10.1016/j.disc.2019.05.015

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An edge coloring of the n-vertex complete graph K-n is a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle whose edges are colored with three distinct colors. We prove that the number of Gallai colorings of K-n with at most three colors is at most 7(n + 1)2((n2)), which improves the best known upper bound of 3/2(n - 1)! . 2((n-12)) in Benevides et al. (2017). (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：2618 / 2631

页数：14

共 31 条

[1] Allen P., 2016, ARXIV161200622
[2] The number of edge colorings with no monochromatic cliques
Alon, N
Balogh, J
Keevash, P
Sudakov, B
[J]. JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2004, 70 : 273 - 288
[3] Counting sum-free sets in abelian groups
Alon, Noga
Balogh, Jozsef
Morris, Robert
Samotij, Wojciech
[J]. ISRAEL JOURNAL OF MATHEMATICS, 2014, 199 (01) : 309 - 344
[4] Alves R. G., 2015, ARXIV150904638
[5] [Anonymous], 1996, SZEMEREDIS REGULARIT
[6] The Number of Subsets of Integers with No k-Term Arithmetic Progression
Balogh, Jozsef
Liu, Hong
Sharifzadeh, Maryam
[J]. INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2017, 2017 (20) : 6168 - 6186
[7] THE NUMBER OF MAXIMAL SUM-FREE SUBSETS OF INTEGERS
Balogh, Jozsef
Liu, Hong
Sharifzadeh, Maryam
Treglown, Andrew
[J]. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2015, 143 (11) : 4713 - 4721
[8] Balogh J, 2015, J AM MATH SOC, V28, P669
[9] The number of the maximal triangle-free graphs
Balogh, Jozsef
Petrickova, Sarka
[J]. BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2014, 46 : 1003 - 1006
[10] The number of K m,m -free graphs
Balogh, Jozsef
Samotij, Wojciech
[J]. COMBINATORICA, 2011, 31 (02) : 131 - 150

← 1 2 3 4 →