{"id":{"repo_id":"brazil-uerj","oai_identifier":"oai:pantheon.ufrj.br:11422/6400"},"canonical_url":"https://search.dev.ndltd.org/etd/brazil-uerj/oai:pantheon.ufrj.br:11422/6400","repository":{"repo_id":"brazil-uerj","name":"Brazil UERJ","base_url":"https://pantheon.ufrj.br/oai/request"},"display":{"title":"Jogos combinatórios em grafos: jogo Timber e jogo de Coloração","abstract":"Studies three competitive combinatorial games. The timber game is played in digraphs, with each arc representing a domino, and the arc direction indicates the direction in which it can be toppled, causing a chain reaction. The player who topples the last domino is the winner. A P-position is an orientation of the edges of a graph in which the second player wins. If the graph has cycles, then the graph has no P-positions and, for this reason, timber game is only interesting when played in trees. We determine the number of P-positions in three caterpillar families and a lower bound for the number of P-positions in any caterpillar. Moreover, we prove that a tree has P-positions if, and only if, it has an even number of edges. In the coloring game, Alice and Bob take turns properly coloring the vertices of a graph, Alice trying to minimize the number of colors used, while Bob tries to maximize them. The game chromatic number is the smallest number of colors that ensures that the graph can be properly colored despite of Bob's intention. We determine the game chromatic number for three forest subclasses (composed by caterpillars), we present two su cient conditions and two necessary conditions for any caterpillar to have game chromatic number equal to 4. In the marking game, Alice and Bob take turns selecting the unselected vertices of a graph, and Alice tries to ensure that for some integer k, every unselected vertex has at most k − 1 neighbors selected. The game coloring number is the smallest k possible. We established lower and upper bounds for the Nordhaus-Gaddum type inequality for the number of P-positions of a caterpillar, the game chromatic and coloring numbers in any graph.","abstract_html":"Studies three competitive combinatorial games. The timber game is played in digraphs, with each arc representing a domino, and the arc direction indicates the direction in which it can be toppled, causing a chain reaction. The player who topples the last domino is the winner. A P-position is an orientation of the edges of a graph in which the second player wins. If the graph has cycles, then the graph has no P-positions and, for this reason, timber game is only interesting when played in trees. We determine the number of P-positions in three caterpillar families and a lower bound for the number of P-positions in any caterpillar. Moreover, we prove that a tree has P-positions if, and only if, it has an even number of edges. In the coloring game, Alice and Bob take turns properly coloring the vertices of a graph, Alice trying to minimize the number of colors used, while Bob tries to maximize them. The game chromatic number is the smallest number of colors that ensures that the graph can be properly colored despite of Bob's intention. We determine the game chromatic number for three forest subclasses (composed by caterpillars), we present two su cient conditions and two necessary conditions for any caterpillar to have game chromatic number equal to 4. In the marking game, Alice and Bob take turns selecting the unselected vertices of a graph, and Alice tries to ensure that for some integer k, every unselected vertex has at most k − 1 neighbors selected. The game coloring number is the smallest k possible. We established lower and upper bounds for the Nordhaus-Gaddum type inequality for the number of P-positions of a caterpillar, the game chromatic and coloring numbers in any graph.","abstract_has_math":false,"creators":["Furtado, Ana Luísa Carvalho"],"institution":"Universidade Federal do Rio de Janeiro","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Figueiredo, Celina Miraglia Herrera de"],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-10","date_published":"2017-10","updated_at":"2026-07-24T01:16:21Z","subjects":["Otimização combinatória","Teoria dos grafos","Teoria dos jogos"],"languages":["por"],"rights":["Acesso Aberto"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11422/6400","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Figueiredo, Celina Miraglia Herrera de"]},{"key":"dc:creator","label":"Author","values":["Furtado, Ana Luísa Carvalho"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-02-06T17:03:32Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-05-16T03:03:30Z"]},{"key":"dc:date.issued","label":"Date","values":["2017-10"]},{"key":"dc:publisher","label":"Institution","values":["Universidade Federal do Rio de Janeiro"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia"]},{"key":"dc:type","label":"Dc Type","values":["Tese"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Otimização combinatória","Teoria dos grafos","Teoria dos jogos"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["por"]},{"key":"dc:rights","label":"Dc Rights","values":["Acesso Aberto"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11422/6400"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Studies three competitive combinatorial games. The timber game is played in digraphs, with each arc representing a domino, and the arc direction indicates the direction in which it can be toppled, causing a chain reaction. The player who topples the last domino is the winner. A P-position is an orientation of the edges of a graph in which the second player wins. If the graph has cycles, then the graph has no P-positions and, for this reason, timber game is only interesting when played in trees. We determine the number of P-positions in three caterpillar families and a lower bound for the number of P-positions in any caterpillar. Moreover, we prove that a tree has P-positions if, and only if, it has an even number of edges. In the coloring game, Alice and Bob take turns properly coloring the vertices of a graph, Alice trying to minimize the number of colors used, while Bob tries to maximize them. The game chromatic number is the smallest number of colors that ensures that the graph can be properly colored despite of Bob's intention. We determine the game chromatic number for three forest subclasses (composed by caterpillars), we present two su cient conditions and two necessary conditions for any caterpillar to have game chromatic number equal to 4. In the marking game, Alice and Bob take turns selecting the unselected vertices of a graph, and Alice tries to ensure that for some integer k, every unselected vertex has at most k − 1 neighbors selected. The game coloring number is the smallest k possible. We established lower and upper bounds for the Nordhaus-Gaddum type inequality for the number of P-positions of a caterpillar, the game chromatic and coloring numbers in any graph."]},{"key":"dc:title","label":"Title","values":["Jogos combinatórios em grafos: jogo Timber e jogo de Coloração"]}]}],"canonical_facts":{"dc:contributor.advisor":["Figueiredo, Celina Miraglia Herrera de"],"dc:creator":["Furtado, Ana Luísa Carvalho"],"dc:date.accessioned":["2019-02-06T17:03:32Z"],"dc:date.available":["2026-05-16T03:03:30Z"],"dc:date.issued":["2017-10"],"dc:description.abstract":["Studies three competitive combinatorial games. The timber game is played in digraphs, with each arc representing a domino, and the arc direction indicates the direction in which it can be toppled, causing a chain reaction. The player who topples the last domino is the winner. A P-position is an orientation of the edges of a graph in which the second player wins. If the graph has cycles, then the graph has no P-positions and, for this reason, timber game is only interesting when played in trees. We determine the number of P-positions in three caterpillar families and a lower bound for the number of P-positions in any caterpillar. Moreover, we prove that a tree has P-positions if, and only if, it has an even number of edges. In the coloring game, Alice and Bob take turns properly coloring the vertices of a graph, Alice trying to minimize the number of colors used, while Bob tries to maximize them. The game chromatic number is the smallest number of colors that ensures that the graph can be properly colored despite of Bob's intention. We determine the game chromatic number for three forest subclasses (composed by caterpillars), we present two su cient conditions and two necessary conditions for any caterpillar to have game chromatic number equal to 4. In the marking game, Alice and Bob take turns selecting the unselected vertices of a graph, and Alice tries to ensure that for some integer k, every unselected vertex has at most k − 1 neighbors selected. The game coloring number is the smallest k possible. We established lower and upper bounds for the Nordhaus-Gaddum type inequality for the number of P-positions of a caterpillar, the game chromatic and coloring numbers in any graph."],"dc:identifier.uri":["http://hdl.handle.net/11422/6400"],"dc:language":["por"],"dc:publisher":["Universidade Federal do Rio de Janeiro"],"dc:publisher.department":["Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia"],"dc:rights":["Acesso Aberto"],"dc:subject":["Otimização combinatória","Teoria dos grafos","Teoria dos jogos"],"dc:title":["Jogos combinatórios em grafos: jogo Timber e jogo de Coloração"],"dc:type":["Tese"]},"updated_at":"2026-07-24T01:16:21Z"}