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.
Recommended Citation
Skinner, Brett, "Some problems on graph colorings" (2018). Dissertations. 161.
https://louis.uah.edu/uah-dissertations/161