QA185 : On Chromatic Index of Hypergraphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2013
Authors:
Abstarct: The chromatic number χ(H) is defined to be the smallest number of colors needed
to color the vertices of H such that no edge Ei of H with |Ei| > 1 has all its vertices
with the same color. The chromatic index χ′(H) of H is the least number of colors
needed to color the edges of H so that no two intersecting edges have the same color.
Although determining the exact chromatic index of hypergraphs is very difficult, in
this thesis we try to determine it through a bound. so, we define the well-known
Shannon’s theorem and introduce its generalization in different states of a hypergraph
to use its results for obtaining different bounds for different kinds of hypergraphs. Even
in many cases, we use the Greedy algorithm for coloring in order to obtain an optimal
bound. For special kinds of k-uniform hypergraphs, we express bound of Alon and
Kim as a conjecture, then we prove it for the special kinds of intersecting k-uniform
hypergraphs. Finally, we use the fact that graphs are a special kind of hypergraphs
and we express the Vizing’s theorem that is the most populor theorem in chromatic
index of graphs, then we use related theorems about chromatic index of graphs and
duality in multigraphs and line graphs to deliver an upper bound for multigraphs.
Also, we use generalized Vizing’s theorem in different kinds of hypergraphs several
times. Some cases are still open.
Keywords:
#hypergraph #chromatic index #chromatic number
Keeping place: Central Library of Shahrood University
Visitor:
Keeping place: Central Library of Shahrood University
Visitor: