The problem of intersection of longest paths in graph classes
Decomposition of a graph into paths: structural and algorithmic aspects
| Full text | |
| Author(s): |
Bastos, Josefran de Oliveira
[1]
;
Benevides, Fabricio Siqueira
[2]
;
Mota, Guilherme Oliveira
[3]
;
Sau, Ignasi
[4]
Total Authors: 4
|
| Affiliation: | [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
Total Affiliations: 4
|
| Document type: | Journal article |
| Source: | DISCRETE MATHEMATICS; v. 342, n. 9, p. 2618-2631, SEP 2019. |
| 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 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. (AU) | |
| FAPESP's process: | 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics |
| Grantee: | Guilherme Oliveira Mota |
| Support Opportunities: | Research Grants - Young Investigators Grants |