Group Connectivity and Group Coloring: A Ph.D. thesis in Graph Theory

Rikke Marie Langhede

Research output: Book/ReportPh.D. thesis

173 Downloads (Pure)

Abstract

This Ph.D. thesis in mathematics concerns group connectivity and group coloring within the general area of graph theory. The contribution consists of the following parts: Weak group connectivity and weak group coloring. We define the weak group connectivity number and the weak group chromatic number and show that these differ from the ordinary group connectivity number and the ordinary group chromatic number. We find examples of graphs where the group connectivity number (resp. the group chromatic number) is almost twice as big as the weak group connectivity number (resp. the weak group chromatic number). We show, however, that there is an upper bound on the group connectivity number (resp. the group chromatic number) given the weak group connectivity number (resp. the weak group chromatic number). We also present some results for groups of small order. Many Z6-flows and exponentially many Z8-flows. Dvořák, Mohar and Šámal proved that there are exponentially many nowhere-zero flows under some conditions. Group connectivity can be seen as an extension of nowhere-zero flows and in this setting we show that there are exponentially many Γ-flows in 3-edge-connected graphs for Abelian groups Γ of order at least 8. We also show that there are at least 2√ℓ/ log ℓ Z6-flows in 3-edge-connected graphs G where ℓ = |E(G)| − |V (G)| ≥ 11. Exponentially many Z5-colorings and Z5-flows. We show that there are exponentially many Z5-colorings in planar simple graphs. The proof is based on an argument by Thomassen previously used to show that there are exponentially many 5-list-colorings, but adapting the proof to group coloring turns out to be highly
nontrivial. The dual result is that there are exponentially many Z5-flows in planar 3-edge-connected graphs. Group colorings with Z4 and Z2 × Z2. We show that there are planar simple graphs which are Z4-colorable, but not Z2 ×Z2-colorable. These graphs are the result of the Hajos’ construction on a non-simple graph with the same property (found by Hušek, Mohelníková and Šámal) and a Z4- and Z2 × Z2-critical graph. We also show that there are planar simple graphs which are Z2 ×Z2-colorable, but not Z4-colorable. The proof is not using a computer, which makes it the first of its kind. In fact, we find graphs which are Zk2-colorable, but not Γ-colorable for any other Abelian group Γ of order |Γ| = 2k. Since the graphs described above are all planar, we get dual results for group connectivity.
Original languageEnglish
PublisherTechnical University of Denmark
Number of pages112
Publication statusPublished - 2020

Fingerprint

Dive into the research topics of 'Group Connectivity and Group Coloring: A Ph.D. thesis in Graph Theory'. Together they form a unique fingerprint.

Cite this