Full program of the event.
- The time reserved for each work is 15 minutes for the presentation plus 5 minutes for questions.
- Plenary sessions last 45 minutes for the presentation plus 5 minutes for questions.
- We request the presenters to bring the slides in a pen-drive or send to us previously (to lawcgmat@gmail.com).
- The event has four Invited Speakers. Details can be found here.
- We will have a Panel Discussion on Monday afternoon on the theme “Popularization of Science: a challenge for theoretical fields”.
- Technical sessions will occur in the two auditoriums of the hotel, named: Aquiraz and Iguape.
- Main sessions such as Opening and Closing ceremonies, plenary talks and our panel discussion will take place at the bigger auditorium: Aquiraz.
Download the Banner of LAWCG 2024.
Download the Annals of LAWCG 2024.
Download the Certificates of Participation
Download the Certificates of Presentation
Download the Certificates of Plenary Talks
| Shortcuts | Monday | Tuesday | Wednesday |
| Morning | Link | Link | Link |
| Afternoon | Link | Link | Link |
Sunday, October 20th, 2024
| Time | Activity |
|---|---|
| 19:30 | Opening Cocktail |
Monday morning, October 21th, 2024
| Time | Activity | |
|---|---|---|
| 09:00 - 09:20 | Opening Ceremony | |
| 09:20 - 10:10 | Plenary Talk: César Hernández Cruz (Chair: Júlio Araújo) | |
| T. Sessions 1 and 2 | Aquiraz (Chair: Júlio Araújo) | Iguape (Chair: Karol Maia) |
| 10:10 - 10:30 | Locally identifying coloring of split graphs. Márcia Cappelle, Hebert Coelho, Robson Medrado de Oliveira. |
Dijkstra Hypergraphs. Leonardo de Almeida Cavadas, Luerbio Faria, André Luiz Pires Guedes, Lilian Markenzon, Lucila Maria de Souza Bento, Jayme Luiz Szwarcfiter. |
| 10:30 - 10:50 | O polinômio cromático do grafo \(C_3 \square P_n\). Mayara Christina, Mauro Nigro, Diana Sasaki. |
Um estudo sobre grafos 2-cordais finos e subclasses. Aline Silva Reis, Vinicius Fernandes dos Santos. |
| 10:50 - 11:20 | Coffee-break | |
| T. Sessions 3 and 4 | Aquiraz (Chair: Nicolas Martins) | Iguape (Chair: Jonas Costa) |
| 11:20 - 11:40 | The oriented chromatic number of a wheel and of the disjoint union of a wheel with a complete graph. Erika Morais Martins Coelho, Luerbio Faria, Mateus de Paula Ferreira, Sylvain Gravier, Sulamita Klein, Hebert Coelho da Silva. |
Some results on the relationship between modular-related parameters of graphs. Vinicius Fernandes dos Santos, Leandro Freitas de Souza |
| 11:40 - 12:00 | About directed backbone colourings of graphs. * Júlio Araújo, Rayane Gomes de Castro, Alexandre Talon*. |
Variations of chordal and dually chordal graphs characterizable by vertex orderings. Kaio Henrique Masse Vieira, Vinicius Fernandes dos Santos. |
| 12:00 - 12:20 | Graceful Coloring of cubic graphs: a focus on Snark families. Simone Dantas, Atílio G. Luiz, Paola T. Pantoja. |
IIC-comparability graphs. Marina Groshaus, André Luiz Pires Guedes. |
| 12:20 - 12:40 | Total-Neighbor-Distinguishing Index by Sums on Generalized Sierpinski graphs. Simone Dantas, Miguel A. Del Rio Palma, Carlos A. Rodríguez Palma. |
When do graph covers preserve the clique dynamics of infinite graphs? Anna Margarethe Limbach, Martin Winter. |
| 12:40 - 14:20 | Lunch |
Monday afternoon, October 21th, 2024
| Time | Activity | |
|---|---|---|
| 12:40 - 14:20 | Lunch | |
| T. Sessions 5 and 6 | Aquiraz (Chair: Victor Campos) | Iguape (Chair: Phablo Moura) |
| 14:20 - 14:40 | Edge Coloring of the Graph \(H_{l,p}\). Athos José de Araújo, Diane Castonguay, André da Cunha Ribeiro. |
Inclusion graphs of biclique parts of \(K_3\)–free graphs. Edmilson Pereira da Cruz, Marina Groshaus, André Luiz Pires Guedes. |
| 14:40 - 15:00 | Preenchendo lacunas na coloração de arestas de grafos split. Diego Amaro Costa, Fernanda Couto, Sulamita Klein. |
Erdős sparse halves conjecture for blow-ups of Vega graphs. César Bispo, Walner Mendonça, Guilherme Mota, Roberto Parente. |
| 15:00 - 15:20 | On the irregular chromatic index of blow-ups of cycles. Pedro Arraes, Guilherme Mota, Carla Lintzmayer, Maycon Sambinelli. |
Estudo sobre 3-atribuição de papéis para produtos direto de grafos. Diane Castonguay, Luiz Felipe Belisário Macedo, Julliano Nascimento. |
| 15:20 - 15:40 | Flow decomposition on arc-coloured networks. Jonas Costa, Cláudia Linhares Sales, Ana Karolinna Maia, Cláudio Soares de Carvalho Neto. |
Transversals of longest paths on cubic pseudo-Halin graphs. Heloisa Lazari, Yoshiko Wakabayashi. |
| 15:40 - 16:00 | Diameter Reduction Via Flipping Arcs. Panna Gehér, Max Kölbl, Lydia Mirabel Mendoza-Cadena, Daniel P. Szabo. |
|
| 16:00 - 16:30 | Coffee-break | |
| 16:30 - 18:00 | Panel: “Popularization of Science: a challenge for theoretical fields”. Cláudia Linhares, Rosiane de Freitas, Nicolas Nisse, Vinícius dos Santos. |
Tuesday morning, October 22th, 2024
| Time | Activity | |
|---|---|---|
| 09:00 - 09:50 | Plenary Talk: Andrea Jiménez (Chair: Guilherme Mota) | |
| T. Sessions 7 and 8 | Aquiraz (Chair: Guilherme Mota) | Iguape (Chair: Karol Maia) |
| 09:50 - 10:10 | Sufficient conditions that ensure trees to have game chromatic number 4. Simone Dantas, Celina Figueiredo, Ana Luísa Carvalho Furtado, Miguel Del Rio Palma. |
The Path Validity Problem. Hebert Coelho, Leslie Richard Foulds, Gustavo Leal, Humberto José Longo. |
| 10:10 - 10:30 | Some results on graph coloring games. Eder Figueiredo, Vinicius Fernandes dos Santos. |
On Finding Temporal Cycles and Acyclic Labelings. Davi de Andrade, Allen Ibiapina, Andrea Marino, Ana Shirley Silva. |
| 10:30 - 10:50 | Results on the connected greedy coloring game. Thiago Marcilon, Ariane Ribeiro. |
Inaproximabilidade do \(k\)-center balanceado. Lehilton Pedrosa, Hugo Kooki Kasuya Rosado. |
| 10:50 - 11:20 | Coffee-break | |
| T. Sessions 9 and 10 | Aquiraz (Chair: Atílio Luiz) | Iguape (Chair: Manoel Campêlo) |
| 11:20 - 11:40 | Infinite families of two Kochol superpositions of Loupekine snarks are Type 1. Simone Dantas, Miguel A.D.R. Palma, Giovanna A.B. Penao, Diana Sasaki. |
Algoritmos exatos para o problema do Número de Grundy. Davi Gomes Florencio, Wladimir Araujo Tavares. |
| 11:40 - 12:00 | On the AVD-total chromatic number of 4-regular circulant graphs. Luerbio Faria, Mauro Nigro, Diana Sasaki. |
Scheduling Transmissions in Time-Slotted LoRa Wide Area Networks. Christelle Caillouet, Frédéric Havet, Lucas Picasarri-Arrieta, Teiki Rigaud. |
| 12:00 - 12:20 | The AVD-total chromatic number of fullerene nanodiscs. Mariana Cruz, Mauro Nigro, Diana Sasaki. |
Graphical Traveling Salesman Problem in some graph classes. Thailsson Clementinio, Rosiane de Freitas Rodrigues. |
| 12:20 - 12:40 | Equitable Total Coloring of Grid Graphs. Sheila Almeida, Nicolas Crisostimo Eusebio. |
Algorithms for the Maximum Clique Problem with Bit-Level Parallelism. Igor Albuquerque, Wladimir Tavares. |
| 12:40 - 14:40 | Lunch |
Tuesday afternoon, October 22th, 2024
| Time | Activity |
|---|---|
| 12:40 - 14:40 | Lunch |
| 14:40 - 15:00 | Photo of the event |
| 15:00 - 17:00 | Social Activities |
| 19:00 - 22:00 | Conference Dinner |
Wednesday morning, October 23th, 2024
| Time | Activity | |
|---|---|---|
| 09:00 - 09:50 | Plenary Talk: Nicolas Nisse (Chair: Rudini Sampaio) | |
| T. Sessions 11 and 12 | Aquiraz (Chair: Rudini Sampaio) | Iguape (Chair: Walner Mendonça) |
| 09:50 - 10:10 | The Firefighter problem on Loupekine snarks. Luerbio Faria, Sérgio Fusquino, Diego Nicodemos, Vinicius Fernandes dos Santos, Diana Sasaki. |
\([k]\)-Roman Domination on Triangulated Discs. Atilio Luiz, Lucas de Araújo Torres. |
| 10:10 - 10:30 | Graph aspects and algorithms of a Tower of Hanoi-London hybrid game. Jonas Costa, Rosiane de Freitas Rodrigues, Lia Martins. |
Double Roman Domination on graphs with maximum degree 3. Atilio Luiz, Francisco Anderson da Silva Vieira. |
| 10:30 - 10:50 | The Harmonious Colouring Game. Cláudia Linhares Sales, Nicolas Martins, Nicolas Nisse. |
Independent locating-dominating sets in some graph classes. Márcia Cappelle, Erika Morais Martins Coelho, Leslie Richard Foulds, Dayllon Vinícius Xavier Lemos, Humberto José Longo. |
| 10:50 - 11:20 | Coffee-break | |
| T. Sessions 13 and 14 | Aquiraz (Chair: Fabricio Benevides) | Iguape (Chair: Wladimir Tavares) |
| 11:20 - 11:40 | Jogos partizan de convexidade em grafos. Samuel Araújo, João Marcos Brito, Raquel Folz, Rosiane de Freitas, Rudini Sampaio. |
Almost All Complementary Prisms Have Many Pairwise-disjoint Perfect Matchings. Leandro Zatesko |
| 11:40 - 12:00 | Convexity Games on Oriented Graphs. Samuel N. de Araújo, João Marcos Brito, Rudini Sampaio. |
Extending a perfect matching to a hamiltonian cycle in some classes of graphs. C. N. Campos, Alessandra Aparecida Pereira. |
| 12:00 - 12:20 | Results on \(f\)-reversible processes. Pedro Fernandes, Thiago Marcilon, Murillo Silva. |
The cost of perfection for matchings in Prism graphs. Ingrid Borchert, Diego Nicodemos, Diana Sasaki. |
| 12:20 - 12:40 | \(W\)-Hierarchy of Geodetic number problem. Simone Dantas, Vitor Dos Santos Ponciano, Rômulo Luiz Oliveira da Silva, Alessandra B. Verissimo |
On the ℓ-Nested Cut problem: a generalization of Matching Cut. Guilherme Castro Mendes Gomes, Gabriel Lucas Costa Martins. |
| 12:40 - 14:20 | Lunch |
Wednesday afternoon, October 23th, 2024
| Time | Activity | |
|---|---|---|
| 12:40 - 14:20 | Lunch | |
| 14:20 - 15:10 | Plenary Talk: Marina Esther Groshaus (Chair: Ana Shirley Silva) | |
| T. Sessions 15 and 16 | Aquiraz (Chair: Ana Shirley Silva) | Iguape (Chair: Thiago Marcilon) |
| 15:10 - 15:30 | Parameterized algorithms for thinness via the cluster module number. Flavia Bonomo, Eric Brandwein, Ignasi Sau. |
On open-independent dominating sets for some subclasses of cubic graphs. Erika Morais Martins Coelho, Lauane Moraes. |
| 15:30 - 15:50 | Chain Traveling Salesmen Problem. Lehilton Pedrosa, Lucas de Oliveira Silva. |
Applying Spectral Graph Theory to Coupled Oscillation problems. Felipe Costa Melo Cunha, Ivan Guilhon, Samuel Madeiro, Antênio José da Costa Sampaio, Rudini Sampaio. |
| 15:50 - 16:20 | Coffee-break | |
| 16:20 - 16:40 | Closing Session |
Invited Speakers
César Hernández Cruz
Universidad Nacional Autónoma de México, Mexico.
Title: Revisiting full homomorphisms
Abstract: For a pair of graphs \(G\) and \(H\), a homomorphism from \(G\) to \(H\) is a function \(f \colon V_G \to V_H\) that preserves adjacencies, i.e., for any pair of vertices \(u\) and \(v\) of \(G\), the existence of the edge \(uv\) in \(G\) implies the existence of the edge \(f(u)f(v)\) in \(H\). A homomorphism is full if it also preserves non-adjacencies (the converse implication in the definition of homomorphism also holds). When \(H\) is a fixed graph, the problem of determining, for an input graph \(G\), the existence of a full homomorphism to \(H\), is often called the full \(H\)-homomorphism problem or the full \(H\)-colouring problem. From the complexity point of view, the full \(H\)-colouring problem has been solved: For any fixed graph \(H\), the full \(H\)-colouring problem is polynomial-time solvable. This classification has deterred further study on full homomorphisms, so little is known in terms of the fine-grained complexity of this problem. In this talk, we will discuss the full \(H\)-colouring problem when \(H\) belongs to some simple families of graphs, showing that really nice complexities can be obtained in some cases.
Short bio: César received bachelor degrees in Mathematics and Computer Science at the National Autonomous University of México (UNAM), and M.Sc. and Ph.D. degrees in Mathematics at the same university. After holding postdoctoral positions at Simon Fraser University in Canada and at UNAM in México, he was a Catedrático CONACYT commissioned to the Autonomous University of Zacatecas and afterwards a CINVESTAV Researcher at the Centre of Research and Advanced Studies of the National Polytechnic Institute in México City. Since December 2019, he is an Associate Professor at the Department of Mathematics in the Faculty of Sciences, UNAM. Although in later years he has worked mainly with hereditary properties of graphs and digraphs, including characterizations, algorithmic and complexity aspects, he has done research in a wide variety of subjects, and keeps an open mind about all areas of graph theory.
Teaching is César’s main activity, besides teaching a broad spectrum of courses in Mathematics and Computer Science, in both undergraduate and graduate programs, he enjoys the personal collaborations that arise in thesis supervisions. He has supervised 14 undergraduate, 6 master and 3 Ph.D. theses, he is currently supervising 6 undergraduate and 1 master theses, as well as a postdoc.
In 2022, César was admitted as a regular member of the Mexican Academy of Sciences, and he was recently appointed as a member of the Editorial Board of Ars Combinatoria.
Andrea Jiménez
Universidad de Valparaíso, Chile.
Title: Graphs with Women
Abstract: The main purpose of this talk is to expose part of my academic life as a graph theorist through the work made in collaboration with great female colleagues.
I plan to tell you who these women are, in which problems we have been working on, and roughly, what we have done together.
Short bio: Andrea completed her bachelor’s degree in mathematics at the University of Valparaíso (UV) in Chile in 2008, after which she studied a Ph.D. in mathematical modeling at the University of Chile, while carrying out several research internships at Charles University, in the Czech Republic. From 2012 she held a postdoctoral position at the University of Sao Paulo (USP) in Brazil and during 2014 she was a visiting researcher at Georgia Tech in Atlanta, US. Currently, Andrea is an Associate Professor at the Institute of Mathematical Engineering at the University of Valparaíso, her alma mater. Andrea coordinates the outreach activities of her academic unit, as well as she coordinates the discrete mathematics research line within the doctoral program in mathematics in consortium (UV-UTFSM-PUCV). Since 2023, Andrea has been part of the board of directors of the Chilean Mathematics Society (SOMACHI).
In her research, Andrea has a strong inclination towards structural graph theory. She has results on graph decompositions, graph colorings, immersions, and many other topics. Currently, Andrea teaches courses on combinatorics, algorithms, and advanced topics in discrete mathematics for undergraduate and graduate students. Together with his colleague, Daniel Quiroz, they supervise two doctoral students.
Andrea is a proud mother of two boys, one 4 years old and the other 9 years old. In her free time she practices Bikram yoga, listens to music, and reads about feminism.
Nicolas Nisse
Inria d’université Côte d’Azur, France.
Title: On some positional games in graphs
Abstract : Maker-Breaker game is a classical 2-Player game where two players, Alice and Bob (starting with Alice), alternately select vertices of an hypergraph. Alice wins if she eventually manages to select all vertices of some hyper-edge. Bob wins otherwise, I.e., if he manages to select all vertices of a transversal of the hyper-edges. The problem of deciding the outcome of the game (who is the winner) is known to be PSPACE complete [Schaefer 1978] even if the hyper-edges have size 6 [Rahman,Watson 2021] and to be polynomial if hyper-edges have size 3 [Galliot,Gravier,Sivignon 24+]. To better understand this game, particular hypergraph classes (defined from graphs) have been studied. For instance, given a graph, we may consider the hypergraph with same vertex set and hyper-edges are the closed neighbourhoods of each vertex (Maker-Breaker domination game) [Duchêne, Gledel, Parreau,Renault 2020]. In this talk, we aim at giving a (far to be exhaustive) overview of these games (and their numerous variants). As examples, we will focus on the Largest Connected Subgraph game (where, given a graph \(G\), Alice aims at selecting the vertices of \(G\) inducing a connected subgraph as large as possible) and on the \(H\)-game (where players select edges instead of vertices and, given a graph \(G\), Alice aims at selecting edges of \(G\) inducing a copy of a fixed graph \(H\)). We will describe some complexity results in various graph classes and we will mainly focus on open problems.
Short bio: Nicolas NISSE is an Inria research director (DR2) at Inria d’Université Côte d’Azur since 2023, in the project-team COATI. He received his engineer diploma from Supélec, in 2004, his Master (2004) and Ph.D. (2007) degrees from LRI, Univ. Paris-Sud 11. He did a postdoc at DIM, Universidad de Chile (07-08) and then at INRIA (08-09). He was Inria researcher from 2009. He received his Habilitation à Diriger des Recherches (HDR) in 2014, from Univ. Nice Sophia Antipolis.
His research interests include graph theory, algorithms and combinatorial optimization. His work mainly focuses on combinatorial games in graphs (graph searching, cops and robber, etc.). He also works on information spreading problems in telecommunication networks (e.g. routing). His expertise concerns the design of algorithms using structural properties (e.g., graph decompositions) and metric properties of networks.
Nicolas Nisse is co-author of about 60 articles in international revues and more than 50 articles in peer reviewed international conference proceedings. He has participated to the PC of several international and national conferences and organized several of them. He supervised 9 Ph.D. theses (one in progress) and more than 50 internships of bachelor/master students. He participated to several national and international projects and, in particular, is currently the head of the Inria associated team CANOE (with UFC). Since 2009, N. Nisse teaches (at least 50 hours per year) graph algorithms in master programs. Finally, he his strongly involved in scientific popularization (see Terra Numerica project).
Marina Esther Groshaus
Universidade Tecnológica Federal do Paraná, Brazil.
Title: Biclique graph on a therapist couch: Analyzing their problems
Abstract: A biclique in a graph is a maximal complete bipartite induced subgraph. The biclique intersection graph was defined over 20 years ago as the biclique graph, \(KB(G)\). Although the class of biclique graphs has a “Kraus Type” characterization, it does not lead to an efficient algorithm for the recognition problem. Furthermore, although we know that the problem is in \(NP\), the computational complexity of the biclique graph recognition problem remains unresolved. Since then, we have focused on better understanding this class, obtaining several partial results that provide different strategies to follow. However, we know that this is a bit complicated class to handle. Therefore, in this presentation, we will sit the biclique graph on the therapist’s couch and share their deeper issues, many of which are still unsolved. We will understand their true essence and be surprised to discover that, despite their difficulty, complexity, and particularity, they are not alone, on the contrary, they are very well related!
Short bio: Marina Groshaus has a mathematician degree (2001), a Phd in Computer Science, both from the University of Buenos Aires (UBA), and a post-doc at Universidade Federal do Paraná (UFPR, 2017). She was a researcher of CONICET (Argentina), and teached at the University of Buenos Aires for 10 years. Nowadays, she is a professor at Universidade Tecnológica Federal do Paraná (UTFPR). She is a researcher in the field of mathematics and computer science. She is known for her work in the area of bicliques of graphs, including characterizations, algorithms, and complexity aspects. Most of the results on bicliques are related to her work.
She has contributed and coordinated various projects in these areas. Marina’s publications envolve researchers from many countries.
She was chair in two editions of LAWCG, helded in Argentina (2012) and Brasil (2022), respectively.
She has been involved in literary works, particularly in the genre of children’s literature.
