The Strong Chromatic Index of Cacti
Date Issued
2012
Date
2012
Author(s)
Liao, Shao-Tang
Abstract
A strong edge coloring of a graph G is an assignment of colors to the edges of G such that two distinct edges are colored differently if their distance is at most two. The strong chromatic index of a graph G, denoted by χ''_s(G) , is the minimum number of colors needed for a strong edge coloring of G. For a graph G, define σ(G)=〖max〗┬(uv∈E(G))〖(d_G (u)+d_G (v)-1)〗, where d_G (x) is the degree of x. A cactus is a connected graph in which every block is an edge or a cycle. In this thesis, we study strong chromatic edge coloring for cacti. In particular, it is proved that for any cactus G, we have χ_s''(G) = σ(G) if the length of any cycle is a multiple of 6; χ_s''(G) ≤ σ(G)+1 if the length of any cycle is even; and χ_s''(G) ≤ " ⌊(3σ(G)-1)/2⌋ in general except the case G = C5.
Keywords: strong chromatic index, cactus, cycle, degree
Subjects
strong chromatic index
cactus
cycle
degree
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
index.html
Size
23.49 KB
Format
HTML
Checksum
(MD5):0d6fe763491f5e985555a10ec93edbcc