关键词：
Edge-connectivity
Linear list r-hued coloring
Restricted edge-connectivity
Strong arc connectivity
r-Hued coloring
摘要：
This dissertation focuses on coloring problems in graphs and connectivity problems in digraphs. We obtain the following advances in both directions. 1. Results in graph coloring. For integers k,r > 0, a (k,r)-coloring of a graph G is a proper coloring on the vertices of G with k colors such that every vertex v of degree d( v) is adjacent to vertices with at least min{d( v),r} different colors. The r-hued chromatic number, denoted by χr(G ), is the smallest integer k for which a graph G has a (k,r)-coloring. For a k-list assignment L to vertices of a graph G, a linear (L,r)-coloring of a graph G is a coloring c of the vertices of G such that for every vertex v of degree d(v), c(v)∈ L(v), the number of colors used by the neighbors of v is at least min{dG(v), r}, and such that for any two distinct colors i and j, every component of G[c –1({i,j})] must be a path. The linear list r-hued chromatic number of a graph G, denoted χℓ L,r(G), is the smallest integer k such that for every k-list L, G has a linear (L,r)-coloring. Let Mad( G) denotes the maximum subgraph average degree of a graph G. We prove the following. (i) If G is a K3,3-minor free graph, then χ2(G) ≤ 5 and χ3(G) ≤ 10. Moreover, the bound of χ2( G) ≤ 5 is best possible. (ii) If G is a P4-free graph, then χr(G) ≤q χ( G) + 2(r – 1), and this bound is best possible. (iii) If G is a P5-free bipartite graph, then χr( G) ≤ rχ(G), and this bound is best possible. (iv) If G is a P5-free graph, then χ2(G) ≤ 2χ(G), and this bound is best possible. (v) If G is a graph with maximum degree Δ, then each of the following holds. (i) If Δ ≥ 9 and Mad(G) < 7/3, then χℓL,r( G) ≤ max{lceil Δ/2 rceil + 1, r + 1}. (ii) If Δ ≥ 7 and Mad(G)< 12/5, then χℓ L,r(G)≤ max{lceil Δ/2 rceil + 2, r + 2}. (iii) If Δ ≥ 7 and Mad(G) < 5/2, then χ ℓL,r(G)≤ max{lcei Δ/2 rceil + 3, r + 3}. (vi) If G is a K 4-minor free graph, then χℓL,r( G) ≤ max{r,lceilΔ/2\rceil} + lceilΔ/2rceil + 2. (vii) Every planar graph G with maximum degree Δ has χℓL,r(G) ≤
万方学位论文
详细信息
CNKI期刊
详细信息
