Universität zu Köln

Digraph Coloring Games and Game-Perfectness

Andres, Stephan Dominique (2007) Digraph Coloring Games and Game-Perfectness. PhD thesis, Universität zu Köln.

[img]
Preview
PDF
Download (1010Kb) | Preview

    Abstract

    In this thesis the game chromatic number of a digraph is introduced as a game-theoretic variant of the dichromatic number. This notion generalizes the well-known game chromatic number of a graph. An extended model also takes into account relaxed colorings and asymmetric move sequences. Game-perfectness is defined as a game-theoretic variant of perfectness of a graph, and is generalized to digraphs. We examine upper and lower bounds for the game chromatic number of several classes of digraphs. In the last part of the thesis, we characterize game-perfect digraphs with small clique number, and prove general results concerning game-perfectness. Some results are verified with the help of a computer program that is discussed in the appendix.

    Item Type: Thesis (PhD thesis)
    Translated abstract:
    AbstractLanguage
    In dieser Arbeit wird die spielchromatische Zahl eines Digraphen als spieltheoretische Variante der dichromatischen Zahl eingeführt. Dieser Begriff verallgemeinert die bekannte spielchromatische Zahl eines Graphen. Ein erweitertes Modell berücksichtigt ebenfalls relaxierte Färbungen sowie asymmetrische Zugfolgen. Spielperfektheit wird als spieltheoretische Variante der Perfektheit eines Graphen definiert und auf Digraphen verallgemeinert. Obere und untere Schranken für die spielchromatische Zahl verschiedener Klassen von Digraphen werden untersucht. Im letzten Teil der Arbeit werden spielperfekte Digraphen mit kleiner Cliquenzahl charakterisiert, sowie allgemeine Resultate über Spielperfektheit gezeigt. Einige Resultate wurden mit Hilfe eines Computerprogramms verifiziert, welches im Anhang diskutiert wird.German
    Creators:
    CreatorsEmail
    Andres, Stephan DominiqueDominique.Andres@FernUni-Hagen.de
    URN: urn:nbn:de:hbz:38-22359
    Subjects: Mathematics
    Uncontrolled Keywords:
    KeywordsLanguage
    spielchromatische Zahl , Digraph , perfekter GraphGerman
    game chromatic number , digraph , perfect graphEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Mathematisches Institut
    Language: English
    Date: 2007
    Date Type: Completion
    Date of oral exam: 29 November 2007
    Full Text Status: Public
    Date Deposited: 08 Feb 2008 08:53:05
    Referee
    NameAcademic Title
    Faigle, UlrichProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/2235

    Actions (login required)

    View Item