Proefschrift Universiteit van Amsterdam. / Met samenvatting in het Engels. - Lit. opg.

abstract: Every graph can be colored with one more color than its maximum degree. A well-known theorem of Brooks gives the precise conditions under which a graph can be colored with maximum degree colors. It is natural to ask for the required conditions on a graph to color with one less color than the maximum degree; in 1977 Borodin and Kostochka conjectured a solution for graphs with maximum degree at least 9: as long as the graph doesn't contain a maximum-degree-sized clique, it can be colored with one fewer than the maximum degree colors. This study attacks the conjecture on multiple fronts. The first technique is an extension of a vertex shuffling procedure of Catlin and is used to prove the conjecture for graphs with edgeless high vertex subgraphs. This general approach also bears more theoretical fruit. The second technique is an extension of a method Kostochka used to reduce the Borodin-Kostochka conjecture to the maximum degree 9 case. Results on the existence of independent transversals are used to find an independent set intersecting every maximum clique in a graph. The third technique uses list coloring results to exclude induced subgraphs in a counterexample to the conjecture. The classification of such excludable graphs that decompose as the join of two graphs is the backbone of many of the results presented here. The fourth technique uses the structure theorem for quasi-line graphs of Chudnovsky and Seymour in concert with the third technique to prove the Borodin-Kostochka conjecture for claw-free graphs. The fifth technique adds edges to proper induced subgraphs of a minimum counterexample to gain control over the colorings produced by minimality. The sixth technique adapts a recoloring technique originally developed for strong coloring by Haxell and by Aharoni, Berger and Ziv to general coloring. Using this recoloring technique, the Borodin-Kostochka conjectured is proved for graphs where every vertex is in a large clique. The final technique is naive probabilistic coloring as employed by Reed in the proof of the Borodin-Kostochka conjecture for large maximum degree. The technique is adapted to prove the Borodin-Kostochka conjecture for list coloring for large maximum degree. / Dissertation/Thesis / Ph.D. Mathematics 2013

No description available.

No description available.

La tesi si concentra sul Partito Nazionalista Cinese negli anni Venti come punto privilegiato di osservazione del cambiamento politico della Cina dopo la Prima guerra mondiale. Questo decennio rappresentò un momento di definizione identitaria sia per i comunisti sia per i nazionalisti. La storiografia ne ha sottolineato numerosi aspetti, ma si è finora occupata del periodo 1919-1928 come una preistoria degli anni Trenta piuttosto che come un autonomo segmento di storia cinese. Studi recenti hanno superato implicitamente questo approccio criticando due date periodizzanti fondamentali per il Novecento cinese: la nascita della Repubblica nazionalista (1911) e la nascita della Repubblica Popolare (1949). A metà tra queste due date, gli anni Venti sono emersi come snodo decisivo nel passaggio da impero a Stato nazionale, durante cui si definì un nuovo spazio di discussione politica. Questo processo, pur interno, subì l’influsso delle strategie internazionali di sovietici e statunitensi dando vita a una nuova visione non soltanto della rivoluzione ma anche dello Stato post-rivoluzionario. Le classi dirigenti nazionalista e comunista, durante la collaborazione, si rivelarono dinamiche e tale “competizione” si trasferì anche all’interno di ciascun movimento diventando un fattore determinante per il successo o il fallimento del partito inteso come moderna formazione politica. / The thesis focuses on the Chinese Nationalist Party in the 1920s as a special standpoint to analyze the political changes in China after the World War I. That decade was crucial for shaping the identity of nationalists and communists. Many works have already examined some aspects, but they mostly considered the years 1919-1928 as a pre-history of the Thirties rather than an autonomous part of Chinese history. Recent studies have overcome this approach by criticizing two of the main periodization in the Chinese twentieth century: the birth of the nationalist Republic (1911) and the birth of the People’s Republic (1949). Halfway, the 1920s stood out as a critical juncture in the transition from empire to nation-state. A new space of political discussion was defined. The process, albeit internal, was under the influence of the USSR and US international strategies and gave birth not only to a new vision of the revolution, but also to a vision of the post-revolutionary state. Also, the nationalist and communist leaderships turned out to be dynamic. That "competition" may be seen also within the two political movements and became a shaping factor for the success or failure of the party as a modern political formation.