QA185 : On Chromatic Index of Hypergraphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2013
Authors:
Azam Shahsavari Najafabadi [Author], Meysam Alishahi[Supervisor], Gholamreza Omidi [Supervisor]
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 Link
Keeping place: Central Library of Shahrood University
Visitor: