Conference Program Latin American Workshop on Cliques in Graphs, 2014 November 9-12 Pirenópolis-GO, Brazil VI Latin American Workshop on Cliques in Graphs, Pirenopólis, Brazil, November 9 – 12, 2014. VI LAWCG VI Latin American Workshop on Cliques in Graphs November 9-12, 2014 Pirenópolis, Goiás, Brazil. Committees Steering Committee: Liliana Alcón – UNLP Celina Herrera de Figueiredo – UFRJ Marina Groshaus – UBA Marisa Gutiérrez – UNLP Miguel Pizaña – UAM Jayme Luiz Szwarcfiter – UFRJ Program Committee: Rommel Melgaço Barbosa – UFG Edson Norberto Cáceres – UFMS Marcelo Henriques Carvalho – UFMS Rosiane de Freitas – UFAM Humberto Longo – UFG Fábio Protti – UFF Organizing Committee: Claudson Ferreira Bornstein – UFRJ Carmen C. Centeno – PUC-GO Hebert Coelho – UFG Leizer de Lima Pinto – UFG André Ribeiro – IFGoiano Local Committee: Diane Castonguay – UFG Elisângela Silva Dias – UFG Márcio Duarte – CAC-UFG Leila Silva – IFGoiano/Morrinhos General Chair: Márcia R. Cappelle – UFG Erika M. M. Coelho – UFG VI Latin American Workshop on Cliques in Graphs, Pirenopólis, Brazil, November 9 – 12, 2014. Sponsors FAPEG – Fundação de Amparo à Pesquisa do Estado de Goiás CNPq – Conselho Nacional de Desenvolvimento Cientı́fico e Tecnológico CAPES – Coordenação de Aperfeiçoamento de Pessoal de Nı́vel Superior Support and Organization UFG – Universidade Federal de Goiás IFGoiano – Instituto Federal Goiano (Campus Rio Verde) PUC-GO – Pontifı́cia Universidade Católica de Goiás UFRJ – Universidade Federal do Rio de Janeiro UFF – Universidade Federal Fluminense UFMS – Universidade Federal de Mato Grosso do Sul UFAM – Universidade Federal do Amazonas VI Latin American Workshop on Cliques in Graphs, Pirenopólis, Brazil, November 9 – 12, 2014. Conference Program November 9th Welcome Ceremony (20:00) Welcome Cocktail (20:30) November 10th Breakfast (7:00 – 8:30) Plenary Talk (8:30 – 9:20) – Room Cavalhadas/Pastorinhas Cliques in Parameterized Hardness Michael R. Fellows Cliques and Bicliques I (9:20 – 10:35) – Room Cavalhadas/Pastorinhas Partitioning Distance Hereditary Graphs into stable sets and cliques João Thompson, Loana Nogueira, Fábio Protti, Raquel Bravo Disimplicial arcs, transitive vertices, and disimplicial eliminations Martiniano Eguı́a, Francisco J. Soulignac Experimental Analysis of Exact Algorithms for the Maximum Clique Problem Cleverson Sebastião dos Anjos, Alexandre Prusch Züge, Renato Carmo Complexity and Algorithms I (9:20 – 10:35) – Room Ita e Alaor Reversible Processes on Graphs Mitre C. Dourado, Carlos V. G. C. Lima, Jayme L. Szwarcfiter On the complexity of the Cluster Deletion problem for several graph classe Flavia Bonomo, Guillermo Durán, Mario Valencia-Pabon Approximative algorithms for the maxcut of chordal graphs Luerbio Faria, Rubens Sucupira, Sulamita Klein Coffee Break (10:35 – 11:00) Coloring I (11:00 – 12:15) – Room Cavalhadas/Pastorinhas Distance coloring problems, spatial properties and feasibility conditions Rosiane de Freitas, Bruno Raphael Dias, Jayme L. Szwarcfiter Choosability for restricted list coloring problems Rosiane de Freitas, Simone Santos, Flavio Coelho, Mario Salvatierra Acyclic edge coloring of the complete bipartite graph K2p,2p Natacha Astromujoff, Martı́n Matamala Graph classes I (11:00 – 12:15) – Room Ita e Alaor Forbidden subgraph characterization of star directed path graphs that are not rooted directed path graphs M. Gutierrez, S. Tondato On the class [h; 2; 2] local L. Alcón, M. Gutierrez, M. P. Mazzoleni VI Latin American Workshop on Cliques in Graphs, Pirenopólis, Brazil, November 9 – 12, 2014. On Restricted Multi-break Rearrangement and Sorting Separable Permutations. Luı́s F. I. Cunha, Rodrigo de A. Hausen, Luis A. B. Kowada, Celina M. H. de Figueiredo Lunch (12:15 – 14:00) Plenary Talk (14:00 – 14:50) – Room Cavalhadas/Pastorinhas On the b-continuity of graphs Márcia R. Cerioli Optional tour: waterfall or Pirenópolis historical center (15:00 – 17:45) Dinner (20:00 – 22:00) November 11th Breakfast (7:00 – 8:30) Plenary Talk (8:30 – 9:20) – Room Cavalhadas/Pastorinhas Cliques, Coloring and Satisfiability: from structure to algorithms Vadim Lozin Convexity (9:20 – 10:35) – Room Cavalhadas/Pastorinhas Periphery and convexity of a graph Danilo Artigas, Simone Dantas, Mitre C. Dourado, Jayme L. Szwarcfiter On the l-neighborhood convexity Carmen C. Centeno, Erika M. M. Coelho, Mitre C. Dourado, Jayme L. Szwarcfiter A tight upper bound for the Helly number of the geodetic convexity on bipartite graphs Mitre Costa Dourado, Aline Rodrigues da Silva Applications (9:20 – 10:35) – Room Ita e Alaor On the diameter of the Cayley Graph Hl,p André C. Ribeiro, Diane Castonguay, Luis Antonio B. Kowada, Celina M. H. Figueiredo Grafos de Permutação Redutı́veis Canônicos: caracterização, reconhecimento e aplicações a marcas d’água digitais Lucila Maria de Souza Bento, Davidson Rodrigo Boccardo, Raphael Carlos Santos Machado, Vinı́cius Gusmão Pereira de Sá, Jayme Luiz Szwarcfiter Sistemas modulares de dı́gitos verificadores ótimos Natália Pedroza de Souza, Paulo Eustáquio Duarte Pinto, Luerbio Faria Coffee Break (10:35 – 11:00) Cliques and Bicliques II (11:00 – 12:15) – Room Cavalhadas/Pastorinhas The Biclique Graph of some classes of graphs II Marina Groshaus, André L. P. Guedes, Juan Pablo Puppo Maximum Clique via MaxSat and Back Again Alexandre Prusch Züge, Renato Carmo Clique and neighborhood characterizations of strongly chordal graphs Pablo De Caria, Terry McKee Coloring II (11:00 – 12:15) – Room Ita e Alaor AVD-total-colouring of some families of snarks Atı́lio Gomes Luiz, C. N. Campos, C. P. de Mello VI Latin American Workshop on Cliques in Graphs, Pirenopólis, Brazil, November 9 – 12, 2014. The Total Coloring of the 3rd and 4th Powers of Cycles S. M. Almeida, J. T. Belotti, M. M. Omai, J. F. H. Brim Complexity of the oriented coloring in planar, cubic oriented graphs Hebert Coelho, Luerbio Faria, Sylvain Gravier, Sulamita Klein Lunch (12:15 – 14:00) Plenary Talk (14:00 – 14:50) – Room Cavalhadas/Pastorinhas A characterization of PM-compact bipartite and near-bipartite graphs Cláudio Lucchesi Complexity and Algorithms II (14:50 – 16:05) – Room Cavalhadas/Pastorinhas Total coloring of snarks is NP-complete Vinı́cius F. dos Santos, Diana Sasaki Complexity between Domination, Independent, Connected, and Paired Domination Numbers Simone Dantas, José D. Alvarado, Dieter Rautenbach Aliança Global Ofensiva em Alguns Produtos Lexicográficos em Grafos Rommel Melgaço Barbosa, Mitre Costa Dourado, Leila Roling Scariot da Silva Combinatorial games and partition (14:50 – 16:05) – Room Ita e Alaor The Burning of the Snarks Simone Dantas, Vitor Costa, Dieter Rautenbach Timber Game with Caterpillars A. Furtado, S. Dantas, C. de Figueiredo, S. Gravier O problema da partição em cliques dominantes H. V. Sousa, Christiane N. Campos Coffee Break (16:05 – 16:30) Posets and Cycles (16:30 – 17:45) – Room Cavalhadas/Pastorinhas Sobre posets representables mediante contencion de caminos en un arbol L. Alcón, N. Gudiño, M. Gutierrez Kneser Graphs are Close to Being Hamiltonian Felipe de Campos Mesquita, Letı́cia Rodrigues Bueno, Rodrigo de Alencar Hausen Hamiltonian Cycles in 4-Connected 4-Regular Claw-free Graphs Jorge L. B. Pucohuaranga, Letı́cia R. Bueno, Daniel M. Martin, Simone Dantas Graph Classes II (16:30 – 17:45) – Room Ita e Alaor Laplacian energy of special families of threshold graphs R. R. Del-Vecchio, C. T. M. Vinagre, G. B. Pereira Adjacent Strong Edge-Coloring of Split-indiference Graphs Aloı́sio de Menezes Vilas-Bôas, Célia Picinin de Mello Maximal Independent sets in cylindrical grid graphs Rommel M. Barbosa, Márcia R. Cappelle Special dinner (20:00 – 00:00) November 12th Breakfast (7:00 – 8:30) VI Latin American Workshop on Cliques in Graphs, Pirenopólis, Brazil, November 9 – 12, 2014. Plenary Talk (8:30 – 9:20) – Room Cavalhadas/Pastorinhas Editing to Cliques: A Survey of FPT Results and Recent Applications in Analyzing Large Datasets Frances Rosamond Cliques and Bicliques III (9:20 – 10:35) – Room Cavalhadas/Pastorinhas On the generalized Helly property of hypergraphs and maximal cliques and bicliques Mitre C. Dourado, Luciano N. Grippo, Martı́n D. Safe The Clique Problem parameterized by the degeneracy of a graph Jonilso Novacoski, Renato Carmo Vizinhança Mı́nima no Hipercubo Moysés da Silva Sampaio Júnior, Paulo Eustáquio Duarte Pinto, Luerbio Faria Complexity and Algorithms III (9:20 – 10:35) – Room Ita e Alaor Enumeration of chordless cycles Diane Castonguay, Elisângela Silva Dias, Walid Abdala Rfaei Jradi, Humberto Longo Algoritmos certificadores e verificadores: testemunhas ausentes e provas computacionais Anne Rose Alves Federici Marinho, Vinı́cius Gusmão Pereira de Sá Solving the k-in-a-tree problem for chordal graphs Vinı́cius F. dos Santos, Murilo V. G. da Silva, Jayme L. Szwarcfiter Coffee Break (10:35 – 11:00) Graph Classes III (11:00 – 12:15) – Room Cavalhadas/Pastorinhas Minimal 4 × 4 M -obstruction cographs Raquel S. F. Bravo, Loana T. Nogueira, Fábio Protti, Jeane Leite Remarks on Complementary Prisms Márcio Antônio Duarte, Lucia Penso, Dieter Rautenbach, Uérverton dos Santos Souza Diameter of a Symmetric Icosahedral Fullerene Graph D. S. Nicodemos, L. Faria, S. Klein Convexity and Intersection Graphs (11:00 – 12:15) – Room Ita e Alaor New results on the geodeticity of the contour of a graph Danilo Artigas, Simone Dantas, Alonso L. S. Oliveira, Thiago M. D. Silva O número de Helly Geodético em convexidades Moisés T. C. Junior, Mitre C. Dourado, Jayme L. Szwarcfiter The problem of recognizing unit PI graphs Luerbio Faria, Luiz Martins, Fabiano Oliveira Lunch (12:15 – 14:00) Check Out (14:00)
Download
