problems in graph theory and probability
Is Version Of
This dissertation is a study of some properties of graphs, based on four journal papers (published, submitted, or in preparation). In the first part, a random graph model associated to scale-free networks is studied. In particular, preferential attachment schemes where the selection mechanism is time-dependent are considered, and an infinite dimensional large deviations bound for the sample path evolution of the empirical degree distribution is found. In the latter part of this dissertation, (edge) colorings of graphs in Ramsey and anti-Ramsey theories are studied. For two graphs, G, and H, an edge-coloring of a complete graph is (G;H)-good if there is no monochromatic subgraph isomorphic to G and no rainbow (totally muticolored) subgraph isomorphic to H in this coloring. Some properties of the set of number of colors used by some (G;H)-colorings are discussed. Then the maximum element in this set when H is a cycle is studied.