Extremal and structural problems in graph theory

• Grant number: 19/13364-7
• Support Opportunities: Regular Research Grants
• Start date: January 01, 2021
• End date: May 31, 2023
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Agreement: Comisión Nacional de Investigación Científica y Tecnológica (CONICYT)
• Principal Investigator: Cristina Gomes Fernandes
• Grantee: Cristina Gomes Fernandes
• Principal researcher abroad: Maya Stein
• Institution abroad: Universidad de Chile , Chile
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• City of the host institution: São Paulo
• Associated researchers: Carla Negri Lintzmayer ; Guilherme Oliveira Mota ; José Coelho de Pina Junior ; Maycon Sambinelli ; Tássio Naia dos Santos ; Yoshiharu Kohayakawa ; Yoshiko Wakabayashi

Abstract

This is a research project for the joint call of proposals between the São Paulo Research Foundation (FAPESP), Brazil, and the Comisión Nacional de Investigación Científica y Tecnológica (CONICYT), Chile. The Brazilian and the Chilean teams have been working in Combinatorics and Graph Theory for several years now. Some of the Brazilian members have already collaborated with some of the Chilean members of the team. This joint application intends to establish and consolidate a cooperation between both teams by working collaboratively on important problems in the areas. The lines of research proposed in this project belong to the field of graph theory and its variants. Graphs are mathematical structures that have applications in a variety of subjects and real-world problems, ranging from computer science over physics to social networks. Our main objective is to study graphs from a theoretical point of view, thus contributing to a better understanding of the laws that govern the behavior of these structures. Progress in this objective should provide new strategies for related problems, as well as make available new techniques for problems in several areas of knowledge. A study of various combinatorial techniques and a good understanding of structural properties of graphs are the pillars of this project, which should lead to the solutions of relevant open problems. The present project will also contribute to the strengthening of the national and international insertion of the involved universities. We remark that the proposed teams contain a mix of young academics with outstanding academic performance and renowned researchers who have extensive experience in the problems to be investigated. (AU)

Scientific publications

(37)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

BOTLER, F.; JIMENEZ, A.; SAMBINELLI, M.; WAKABAYASHI, Y.. On the Structure of a Smallest Counterexample and a New Class Verifying the 2-Decomposition Conjecture. GRAPHS AND COMBINATORICS, v. 40, n. 5, p. 21-pg., 2024-10-01. (15/11937-9, 19/13364-7)

BARROS, GABRIEL FERREIRA; CAVALAR, BRUNO PASQUALOTTO; KOHAYAKAWA, YOSHIHARU; NAIA, TASSIO. ORIENTATION RAMSEY THRESHOLDS FOR CYCLES AND CLIQUES. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 35, n. 4, p. 2844-2857, 2021. (19/13364-7, 18/05557-7, 18/04876-1)

BOTLER, FABIO; JIMENEZ, ANDREA; SAMBINELLI, MAYCON; WAKABAYASHI, YOSHIKO; FERREIRA, CE; LEE, O; MIYAZAWA, FK. The 2-Decomposition Conjecture for a new class of graphs. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 9-pg., 2021-01-01. (15/11937-9, 19/13364-7, 17/23623-4)

NAIA, TASSIO. Trees contained in every orientation of a graph. ELECTRONIC JOURNAL OF COMBINATORICS, v. 29, n. 2, p. 5-pg., 2022-05-06. (19/04375-5, 18/04876-1, 19/13364-7)

BOTLER, FABIO; MOURA, PHABLO F. S.; NAIA, TASSIO. Seymour's Second Neighborhood Conjecture for orientations of (pseudo)random graphs. DISCRETE MATHEMATICS, v. 346, n. 12, p. 12-pg., 2023-12-01. (20/16570-4, 19/04375-5, 19/13364-7)

BOTLER, FABIO; COLUCCI, LUCAS; KOHAYAKAWA, YOSHIHARU. The mod k chromatic index of random graphs. JOURNAL OF GRAPH THEORY, v. 103, n. 4, p. 13-pg., 2023-03-08. (18/04876-1, 20/08252-2, 15/11937-9, 19/13364-7)

BOTLER, FABIO; HOPPEN, CARLOS; MOTA, GUILHERME OLIVEIRA. Counting orientations of graphs with no strongly connected tournaments. DISCRETE MATHEMATICS, v. 345, n. 12, p. 13-pg., 2022-08-05. (18/04876-1, 19/13364-7)

BUSTAMANTE, SEBASTIAN; QUIROZ, DANIEL A.; STEIN, MAYA; ZAMORA, JOSE. Clique immersions and independence number. EUROPEAN JOURNAL OF COMBINATORICS, v. 106, p. 9-pg., 2022-08-19. (19/13364-7)

ROJAS ANRIQUEZ, ALBERTO; STEIN, MAYA. 3-Colouring P-t-Free Graphs Without Short Odd Cycles. ALGORITHMICA, v. N/A, p. 23-pg., 2022-10-17. (19/13364-7)

CAMPOS, MARCELO; COLLARES, MAURICIO; MOTA, GUILHERME OLIVEIRA. Counting orientations of random graphs with no directed k-cycles. RANDOM STRUCTURES & ALGORITHMS, v. 64, n. 3, p. 16-pg., 2023-11-07. (19/13364-7, 18/04876-1)

QUIROZ, DANIEL A.. Clique immersions in graphs of independence number two with certain forbidden subgraphs. DISCRETE MATHEMATICS, v. 344, n. 6, p. 9-pg., 2021-03-17. (19/13364-7)

BOTLER, FABIO; COLUCCI, LUCAS; KOHAYAKAWA, YOSHIHARU. The mod k chromatic index of graphs is O(k). JOURNAL OF GRAPH THEORY, v. 102, n. 1, p. 4-pg., 2022-07-30. (18/04876-1, 19/13364-7, 15/11937-9, 20/08252-2)

FERNANDES, CRISTINA G.; NAIA, TASSIO; SANTOS, GIOVANNE; STEIN, MAYA. Packing large balanced trees into bipartite graphs. DISCRETE MATHEMATICS, v. 348, n. 12, p. 8-pg., 2025-12-01. (19/13364-7)

BOTLER, F.; JIMENEZ, A.; LINTZMAYER, C. N.; PASTINE, A.; QUIROZ, D. A.; SAMBINELLI, M.. Biclique immersions in graphs with independence number 2. EUROPEAN JOURNAL OF COMBINATORICS, v. 122, p. 16-pg., 2024-08-12. (19/13364-7)

PAVEZ-SIGNE, MATIAS; SANHUEZA-MATAMALA, NICOLAS; STEIN, MAYA. Dirac-type conditions for spanning bounded-degree hypertrees. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 165, p. 45-pg., 2023-11-22. (19/13364-7)

ALVARADO, JOSE D.; KOHAYAKAWA, YOSHIHARU; MORRIS, PATRICK; MOTA, GUILHERME OLIVEIRA. A canonical Ramsey theorem with list constraints in random graphs. XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, v. 224, p. 7-pg., 2023-01-01. (18/04876-1, 19/13364-7, 20/10796-0)

BOTLER, FABIO; FERNANDES, CRISTINA G.; GUTIERREZ, JUAN. Independent Dominating Sets in Planar Triangulations. ELECTRONIC JOURNAL OF COMBINATORICS, v. 31, n. 2, p. 10-pg., 2024-04-19. (19/13364-7)

ALVARADO, JOSE D.; KOHAYAKAWA, YOSHIHARU; LANG, RICHARD; MOTA, GUILHERME OLIVEIRA; STAGNI, HENRIQUE. Resilience for loose Hamilton cycles. XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, v. 224, p. 8-pg., 2023-01-01. (18/04876-1, 21/11020-9, 19/13364-7, 20/10796-0)

STEIN, MAYA. Kalai's conjecture in r-partite r-graphs. EUROPEAN JOURNAL OF COMBINATORICS, v. 117, p. 7-pg., 2024-01-13. (19/13364-7)

STEIN, MAYA; ZARATE-GUEREN, CAMILA. Antidirected subgraphs of oriented graphs. COMBINATORICS PROBABILITY & COMPUTING, v. N/A, p. 21-pg., 2024-03-06. (19/13364-7)

BOTLER, FABIO; HOPPEN, CARLOS; MOTA, GUILHERME OLIVEIRA; FERREIRA, CE; LEE, O; MIYAZAWA, FK. Counting orientations of graphs with no strongly connected tournaments. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 9-pg., 2021-01-01. (18/04876-1, 19/13364-7)

REED, BRUCE; STEIN, MAYA. Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result. JOURNAL OF GRAPH THEORY, v. 102, n. 4, p. 47-pg., 2022-10-07. (19/13364-7)

KOHAYAKAWA, YOSHIHARU; MOTA, GUILHERME OLIVEIRA; PARCZYK, OLAF; SCHNITZER, JAKOB. The anti-Ramsey threshold of complete graphs. DISCRETE MATHEMATICS, v. 346, n. 5, p. 12-pg., 2023-02-01. (18/04876-1, 19/13364-7)

COLLARES, MAURICIO; KOHAYAKAWA, YOSHIHARU; MOREIRA, CARLOS GUSTAVO; MOTA, GUILHERME OLIVEIRA; FERREIRA, CE; LEE, O; MIYAZAWA, FK. Constrained colourings of random graphs. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 8-pg., 2021-01-01. (18/04876-1, 19/13364-7)

FERNANDES, CRISTINA G.; LINTZMAYER, CARLA N.; MOURA, PHABLO F. S.. Approximations for the Steiner Multicycle Problem. LATIN 2022: THEORETICAL INFORMATICS, v. 13568, p. 16-pg., 2022-01-01. (19/13364-7)

STEIN, MAYA; ZARATE-GUEREN, CAMILA. SEMIDEGREE, EDGE DENSITY AND ANTIDIRECTED SUBGRAPHS. PROCEEDINGS OF THE 12TH EUROPEAN CONFERENCE ON COMBINATORICS, GRAPH THEORY AND APPLICATIONS, EUROCOMB 2023, v. N/A, p. 7-pg., 2023-01-01. (19/13364-7)

BOTLER, F.; JIMENEZ, A.; LINTZMAYER, C. N.; PASTINE, A.; QUIROZ, D. A.; SAMBINELLI, M.. BICLIQUE IMMERSIONS IN GRAPHS WITH INDEPENDENCE NUMBER 2. PROCEEDINGS OF THE 12TH EUROPEAN CONFERENCE ON COMBINATORICS, GRAPH THEORY AND APPLICATIONS, EUROCOMB 2023, v. N/A, p. 9-pg., 2023-01-01. (19/13364-7)

FERNANDES, CRISTINA G.; MOTA, GUILHERME OLIVEIRA; SANHUEZA-MATAMALA, NICOLAS. Separating Path Systems in Complete Graphs. RANDOM STRUCTURES & ALGORITHMS, v. 66, n. 3, p. 19-pg., 2025-05-01. (18/04876-1, 19/13364-7)

BARROS, GABRIEL FERREIRA; CAVALAR, BRUNO PASQUALOTTO; KOHAYAKAWA, YOSHIHARU; MOTA, GUILHERME OLIVEIRA; NAIA, TASSIO. DIRECTED GRAPHS WITH LOWER ORIENTATION RAMSEY THRESHOLDS. RAIRO-OPERATIONS RESEARCH, v. 58, n. 4, p. 13-pg., 2024-09-09. (18/05557-7, 18/04876-1, 20/16570-4, 19/13364-7, 19/04375-5)

FERNANDES, CRISTINA G.; MOTA, GUILHERME OLIVEIRA; SANHUEZA-MATAMALA, NICOLAS. Separating Path Systems in Complete Graphs. LATIN 2024: THEORETICAL INFORMATICS, PT II, v. 14579, p. 16-pg., 2024-01-01. (19/13364-7)

QUIROZ, DANIEL A.; FERREIRA, CE; LEE, O; MIYAZAWA, FK. Complete immersions in graphs with independence number two and small forbidden subgraphs. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 7-pg., 2021-01-01. (19/13364-7)

JIMENEZ, A.; KNAUER, K.; LINTZMAYER, C. N.; MATAMALA, M.; PENA, J. P.; QUIROZ, D. A.; SAMBINELLI, M.; WAKABAYASHI, Y.; YU, W.; ZAMORA, J.. Boundedness for proper conflict-free and odd colorings. DISCRETE MATHEMATICS, v. 349, n. 2, p. 16-pg., 2026-02-01. (23/03167-5, 19/13364-7)

BOTLER, FABIO; FERNANDES, CRISTINA G.; GUTIERREZ, JUAN. INDEPENDENT DOMINATING SETS IN PLANAR TRIANGULATIONS. PROCEEDINGS OF THE 12TH EUROPEAN CONFERENCE ON COMBINATORICS, GRAPH THEORY AND APPLICATIONS, EUROCOMB 2023, v. N/A, p. 6-pg., 2023-01-01. (19/13364-7)

FERNANDES, CRISTINA G.; LINTZMAYER, CARLA N.; MOURA, PHABLO F. S.. Approximations for the Steiner Multicycle problem. THEORETICAL COMPUTER SCIENCE, v. 1020, p. 16-pg., 2024-09-10. (19/13364-7)

ARAUJO, PEDRO; MARTINS, TAISA; MATTOS, LETICIA; MENDONCA, WALNER; MOREIRA, LUIZ; MOTA, GUILHERME O.. On the Anti-Ramsey Threshold for Non-Balanced Graphs. ELECTRONIC JOURNAL OF COMBINATORICS, v. 31, n. 1, p. 21-pg., 2024-03-22. (18/04876-1, 23/07695-6, 19/13364-7)

KOHAYAKAWA, YOSHIHARU; MENDONCA, WALNER; MOTA, GUILHERME OLIVEIRA; SCHUELKE, BJARNE. COVERING 3-EDGE-COLORED RANDOM GRAPHS WITH MONOCHROMATIC TREES. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 35, n. 2, p. 1447-1459, 2021. (18/04876-1, 19/13364-7)

CHANG, YULIN; HAN, JIE; KOHAYAKAWA, YOSHIHARU; MORRIS, PATRICK; MOTA, GUILHERME OLIVEIRA. Factors in randomly perturbed hypergraphs. RANDOM STRUCTURES & ALGORITHMS, v. 60, n. 2, JUL 2021. (19/13364-7, 18/04876-1)