Author

Brett Skinner

Date of Award

2018

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Mathematical Sciences

Committee Chair

Grant Zhang

Committee Member

Brendan Ames

Committee Member

Carmeliza Navasca

Committee Member

Sivaguru Ravindran

Committee Member

Huaming Zhang

Subject(s)

Graph theory., Graph coloring.

Abstract

Let G be a simple graph. The open neighborhood of a vertex v in G is the set of vertices adjacent to v, denoted as N(v), and the degree of v, denoted as deg(v), is the size of N(v). The maximum degree of a graph, ∆ = ∆(G), is the maximum deg(v) among all vertices in G. The closed neighborhood, N[v], is the set N(v)∪{v}. A proper vertex coloring is an assignment of colors to the vertices of G such that no two adjacent vertices receive the same color. The minimum number of colors required to properly color G is called the chromatic number of G and denoted χ(G). Given a vertex coloring of G, the open coloring neighborhood of v is defined as the set of colors received by N(v) and denoted C(v). Similarly, the closed coloring neighborhood of v, denoted as C[v], is the set of colors received by N[v]. A strong coloring is a proper vertex coloring with the added condition that C[v]≠C[u] whenever u∼v and N[v]≠N[u]. A graph G is said to be color-perfect if χ(G) =χs(G) and k-color-perfect if χ(G) =χs(G) =k. We characterize four-color-perfect graphs of order at least 5 and obtain the unique four-color-perfect graph with 18 vertices and 34 edges. We also show that there exist k-color-perfect graphs for every k≥4. Graphs with high strong chromatic numbers in terms of maximum degrees are constructed using cyclic finite projective planes. We then develop algorithms to produce a strong coloring of G. By analyzing this algorithm, we obtain upper bounds on the strong chromatic number in terms of ∆(G). Tighter upper bounds on χs(G) are also obtained when G is triangle-free and when ∆(G) = 3. A hypergraph H is a set of vertices V(H) together with a collection E(H) of subsets of V(H) called edges. Two vertices u and v are adjacent if there is an edge that contains both u and v, and two edges in H are adjacent if they have at least one vertex in common. The clique graph of a hypergraph H,C(H), is the graph G whose vertex set is V(H) such that two vertices are adjacent in G if they are adjacent in H. We define the clique degree of a vertex x, denoted as D_H(x), to be the degree of x in C(H). The maximum clique degree of H, ∆(H), is the maximum clique degree among all vertices in H. A hypergraph H is said to be linear if every edge has size at least 2 and every pair of vertices is contained in at most one edge. A proper edge coloring of a hypergraph is an assignment of colors to the edges of H such that no two adjacent edges receive the same color. The minimum number of colors required to properly edge color a hypergraph H is called the chromatic index of H and denoted χ′(H). The well known Erdős–Faber–Lovász conjecture says that for any linear hypergraph H, the chromatic index of H is no more than |V(H)|. This conjecture can be generalized to say that for any linear hypergraph H, χ′(H)≤∆(H) + 1. We show that the generalized conjecture is true when ∆(H)≤5. We also show that χ′(G)≤7∆/4−1.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.