## Dissertations

#### Title

Some problems on graph colorings

2018

Dissertation

#### Degree Name

Doctor of Philosophy (PhD)

#### Department

Mathematical Sciences

Grant Zhang

Brendan Ames

#### Committee Member

Carmeliza Navasca

#### Committee Member

Sivaguru Ravindran

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.

COinS