Jackson and Wormald show that every 3-connected K_1,d-free graph, on n vertices, contains a cycle of length at least 1/2 n^g(d) where g(d) = (log_2 6 + 2 log_2 (2d+1))^-1. For d = 3, g(d) ~ 0.122. Improving this bound, we prove that if G is a 3-connected claw-free graph on at least 6 vertices, then there exists a cycle C in G such that |E(C)| is at least c n^g+5, where g = log_3 2 and c > 1/7 is a constant. To do this, we instead prove a stronger theorem that requires the cycle to contain two specified edges. We then use Tutte decomposition to partition the graph and then use the inductive hypothesis of our theorem to find paths or cycles in the different parts of the decomposition.

Made available in DSpace on 2016-04-04T18:36:17Z (GMT). No. of bitstreams: 1 Amarildo 1.pdf: 1027238 bytes, checksum: 8b075fb7f90f3c79a5944a0496350b66 (MD5) Previous issue date: 2006-05-26 / Analyses of the relationship between capital and knowledge in the capitalist system, has been the focus for researches to its historical origin, and the form in which has been developed along the time, to understand how this relation affects the life of the workers and how the technological innovation is affecting the society and its future, With this objective in mind, the idea of long cycles will be used, as initially described by Kondratieff and, later by Schumpeter, and to understand the way these cycles had influences the relation between capital-work and knowledge, mainly if it relates to the gradual appropriation, on the part of the capital the knowledge generated by the workers. The Idea of this study is focused on understanding the way the new information technology specially the advances in electronics and information nets tends to affect the relationship between the capital and work. As these facilitate the development of the so called elite workers, the diligent calls "workers of the knowledge", in the same way that it provokes an increasing exclusion of the less qualified labor. / An?lise da rela??o entre capital e conhecimento no sistema capitalista, buscando sua origem hist?rica e a forma como ela tem se desenvolvido ao longo do tempo, para entender como esta rela??o afeta a vida dos trabalhadores ou ainda, como as inova??es tecnol?gicas v?em afetando a sociedade atual e como poder? afetar seu futuro. Com este objetivo, ser? utilizado a id?ia de ciclos longos, inicialmente descrito por Kondratieff e, posteriormente retomado por Schumpeter, para entender a maneira como estes ciclos influenciaram a rela??o capital-trabalho-conhecimento, principalmente no que se refere ? progressiva apropria??o, por parte do capital, do conhecimento gerado pelos trabalhadores. O esfor?o final deste estudo estar? voltado para a compreens?o da maneira pela qual as novas tecnologias de informa??o, notadamente as baseadas nos avan?os da eletr?nica e redes de informa??o, tendem a afetar as rela??es entre o capital e o trabalho e tamb?m como estas facilitam o desenvolvimento de uma elite de trabalhadores, os chamados trabalhadores do conhecimento , da mesma forma que provoca uma crescente exclus?o da m?o-de-obra de baixa qualifica??o.