| Full text | |
| Author(s): |
Botler, Fabio
;
Colucci, Lucas
;
Kohayakawa, Yoshiharu
Total Authors: 3
|
| Document type: | Journal article |
| Source: | JOURNAL OF GRAPH THEORY; v. 102, n. 1, p. 4-pg., 2022-07-30. |
| Abstract | |
Let chi(k)'(G) denote the minimum number of colors needed to color the edges of a graph G in a way that the subgraph spanned by the edges of each color has all degrees congruent to 1 (mod k). Scott proved that chi(k)'(G) <= 5k(2) log k, and thus settled a question of Pyber, who had asked whether chi(k)'(G) can be bounded solely as a function of k. We prove that chi(k)'(G) = O(k), answering affirmatively a question of Scott. (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 |
| FAPESP's process: | 19/13364-7 - Extremal and structural problems in graph theory |
| Grantee: | Cristina Gomes Fernandes |
| Support Opportunities: | Regular Research Grants |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 20/08252-2 - Extremal and probabilistic problems in graph colorings |
| Grantee: | Lucas Colucci Cavalcante de Souza |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |