Graph Coloring Applications and Defining Sets in Graph Theory

  • Abstract The main theme of this thesis is about Graph Coloring Applications and Defining Sets in Graph Theory. As in the case of block designs, finding defining sets seems to be difficult problem, and there is not a general conclusion. Hence we confine us here to some special types of graphs like bipartite graphs, complete graphs, etc. In this work, four new concepts of defining sets are introduced: • Defining sets for perfect (maximum) matchings • Defining sets for independent sets • Defining sets for edge colorings • Defining set for maximal (maximum) clique Furthermore, some algorithms to find and construct the defining sets are introduced. A review on some known kinds of defining sets in graph theory is also incorporated, in chapter 2 the basic definitions and some relevant notations used in this work are introduced. chapter 3 discusses the maximum and perfect matchings and a new concept for a defining set for perfect matching. Different kinds of graph colorings and their applications are the subject of chapter 4. Chapter 5 deals with defining sets in graph coloring. New results are discussed along with already existing research results, an algorithm is introduced, which enables to determine a defining set of a graph coloring. In chapter 6, cliques are discussed. An algorithm for the determination of cliques using their defining sets. Several examples are included.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Masoumeh Ahadi Moghaddam
URN:urn:nbn:de:hbz:386-kluedo-46127
Advisor:Dietmar Schweigert
Document Type:Doctoral Thesis
Language of publication:English
Date of Publication (online):2017/03/06
Year of first Publication:2001
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2001/09/28
Date of the Publication (Server):2017/03/06
Page Number:87
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0)