The number of Gallai k-colorings of complete graphs

Josefran de Oliveira Bastos; Fabrício Siqueira Benevides; Jie Han

doi:10.1016/j.jctb.2019.12.004

The number of Gallai k-colorings of complete graphs

Josefran de Oliveira Bastos
, Fabrício Siqueira Benevides
, Jie Han

Universidade Federal do Ceará
University of Rhode Island

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

Abstract

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 for n large and every k with k≤2^n/4300, the number of Gallai colorings of K_n that use at most k given colors is ((k2)+o_n(1))2⁽ⁿ²⁾. Our result is asymptotically best possible and implies that, for those k, almost all Gallai k-colorings use only two colors. However, this is not true for k≥2^n/2.

Original language	English
Pages (from-to)	1-13
Number of pages	13
Journal	Journal of Combinatorial Theory. Series B
Volume	144
DOIs	https://doi.org/10.1016/j.jctb.2019.12.004
Publication status	Published - Sept 2020
Externally published	Yes

Keywords

Complete graphs
Counting
Gallai colorings
Rainbow triangles

Access to Document

10.1016/j.jctb.2019.12.004

Cite this

@article{729dc3e2b758460eae125ca26d740af3,

title = "The number of Gallai k-colorings of complete graphs",

abstract = "An edge coloring of the n-vertex complete graph, Kn, 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 for n large and every k with k≤2n/4300, the number of Gallai colorings of Kn that use at most k given colors is ((k2)+on(1))2(n2). Our result is asymptotically best possible and implies that, for those k, almost all Gallai k-colorings use only two colors. However, this is not true for k≥2n/2.",

keywords = "Complete graphs, Counting, Gallai colorings, Rainbow triangles",

author = "Bastos, \{Josefran de Oliveira\} and Benevides, \{Fabr{\'i}cio Siqueira\} and Jie Han",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

year = "2020",

month = sep,

doi = "10.1016/j.jctb.2019.12.004",

language = "English",

volume = "144",

pages = "1--13",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - The number of Gallai k-colorings of complete graphs

AU - Bastos, Josefran de Oliveira

AU - Benevides, Fabrício Siqueira

AU - Han, Jie

PY - 2020/9

Y1 - 2020/9

N2 - An edge coloring of the n-vertex complete graph, Kn, 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 for n large and every k with k≤2n/4300, the number of Gallai colorings of Kn that use at most k given colors is ((k2)+on(1))2(n2). Our result is asymptotically best possible and implies that, for those k, almost all Gallai k-colorings use only two colors. However, this is not true for k≥2n/2.

AB - An edge coloring of the n-vertex complete graph, Kn, 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 for n large and every k with k≤2n/4300, the number of Gallai colorings of Kn that use at most k given colors is ((k2)+on(1))2(n2). Our result is asymptotically best possible and implies that, for those k, almost all Gallai k-colorings use only two colors. However, this is not true for k≥2n/2.

KW - Complete graphs

KW - Counting

KW - Gallai colorings

KW - Rainbow triangles

UR - https://www.scopus.com/pages/publications/85077378198

U2 - 10.1016/j.jctb.2019.12.004

DO - 10.1016/j.jctb.2019.12.004

M3 - Article

AN - SCOPUS:85077378198

SN - 0095-8956

VL - 144

SP - 1

EP - 13

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

The number of Gallai k-colorings of complete graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this