University of Notre Dame
Browse

File(s) under permanent embargo

Some problems involving H-colorings of graphs

thesis
posted on 2013-04-12, 00:00 authored by John Engbers

For graphs G and H , an H -coloring of G, or homomorphism from G to H , is an edge-preserving map from the vertices of G to the vertices of H . H -colorings generalize such graph theory notions as proper colorings and independent sets. In this dissertation, we consider four questions involving H -colorings of graphs.

Recently, Galvin [27] showed that the maximum number of independent sets in an n vertex minimum degree δ graph occurs (for sufficiently large n) when G = Kδ,n−δ. First, we show this result holds for level sets: for all triples (n, δ, t) with δ ≤ 3 and t ≥ 3, no n-vertex graph with minimum degree δ admits more independent sets of size t than Kδ,n−δ, and we obtain the same conclusion for δ > 3 and t ≥ 2δ + 1.

Second, we begin the project of generalizing Galvin?s result to arbitrary H . Writing hom(G, H ) for the number of H -colorings of G, we show that for δ = 1 and δ = 2 and fixed H ,

hom(G, H ) ≤ max{hom(Kδ+1, H ) n/δ+1 , hom(Kδ,δ, H ) 2δ , hom(Kδ,n−δ, H )}

for any n vertex minimum degree δ graph G (for sufficiently large n). For δ ≥ 3 (and sufficiently large n), we provide a class of H for which hom(G, H ) ≤ hom(Kδ,n−δ, H ) for any G in this family.

Third, for a given H , k ∈ V (H ), and regular bipartite G, we consider the pro- portion of vertices of G that get mapped to k in a uniformly chosen H -coloring of G. We find numbers 0 ≤ a−(k) ≤ a+(k) ≤ 1 with the property that for all such G, with high probability the proportion is between a−(k) and a+(k), and we give examples where these extremes are achieved.

Fourth, we study the set of H -colorings of the even discrete torus Zdm. For any H and fixed m, we show that the space of H -colorings of Zdm may be partitioned into a subset of negligible size (as d grows) and a collection of subsets indexed by certain pairs (A, B) ∈ V (H)2, with each H -coloring in the subset indexed by (A, B) having almost all vertices in one partition class mapped to A and almost all vertices in the other partition class mapped to B.

History

Date Modified

2017-06-05

Defense Date

2013-04-11

Research Director(s)

David Galvin

Committee Members

Andrzej Dudek Roxana Smarandache Zoltan Toroczkai

Degree

  • Doctor of Philosophy

Degree Level

  • Doctoral Dissertation

Language

  • English

Alternate Identifier

etd-04122013-100730

Publisher

University of Notre Dame

Program Name

  • Mathematics

Usage metrics

    Dissertations

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC