Abstract
dc:description.abstractThe Borodin–Kostochka Conjecture states that for a graph G, if ∆(G) ≥ 9 and ω(G) ≤ ∆(G) − 1, then χ(G) ≤ ∆(G) − 1. We prove the Borodin–Kostochka Conjecture for (P5, gem)-free graphs, i.e., graphs with no induced P5 and no induced K1 ∨P4. For a graph G and t, k ∈ Z+ at-tone k-coloring of G is a function f : V (G) → [k] such that |f(v) ∩f (w)| < d(v,w) for all distinct v, w ∈ V(G). The t-tone chromatic number of G, denoted τt(G), is the minimum k such that G is t-tone k-colorable. For small values of t, we prove sharp or nearly sharp upper bounds on the t-tone chromatic number of various classes of sparse graphs. In particular, we determine τ2(G) exactly when mad(G) < 12/5 and also determine τ2(G), up to a small additive constant, when G is outerplanar. Finally, we determine τt(Cn) exactly when t ∈ {3, 4, 5}.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy
- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Systems Modeling and Analysis
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- LaFayette, Hudson
- Contributors dc:contributor
-
- Daniel Cranston
- Jessica McDonald
- Neal Bushaw
- Craig Larson
- J. Paul Brooks
Subjects
dc:subject × 5Rights
dc:rights- Statement dc:rights
-
- © The Author
Identifiers
dc:identifier.*- Identifier
- https://scholarscompass.vcu.edu/etd/7442