Decomposition of a graph into paths: structural and algorithmic aspects
The problem of intersection of longest paths in graph classes
| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Fed Ceara, Engn Comp, Fortaleza, Ceara - Brazil
[2] Univ Fed Ceara, Dept Matemat, Fortaleza, Ceara - Brazil
[3] Univ Rhode Isl, Dept Math, Kingston, RI 02881 - USA
Total Affiliations: 3
|
| Document type: | Journal article |
| Source: | JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 144, p. 1-13, SEP 2020. |
| Web of Science Citations: | 0 |
| 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 (((k)(2)) + o(n) (1)) 2((2n)). 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). (C) 2020 Elsevier Inc. All rights reserved. (AU) | |
| FAPESP's process: | 14/18641-5 - Hamilton cycles and tiling problems in hypergraphs |
| Grantee: | Jie Han |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |