Back to search

University of Ioannina

Χαρακτηρισμός νέων κλάσεων τέλειων γραφημάτων και αγλόριθμοι χρωματισμού και μέγιστων διαδρομών

Abstract

dc:description

In this work we provide characterizations of two new classes of perfect graphs, namely colinear and linear graphs. Moreover, we present polynomial-time algorithms or NP-completeness results for various types of the coloring problem on graphs and polynomial-time algorithms for the longest path problem on perfect graphs. In particular, motivated by the de nition of linear coloring on simplicial complexes, recently introduced in the context of algebraic topology, we introduce the colinear coloring on graphs, and propose a polynomial algorithm for colinearly coloring any graph G. Based on the colinear coloring, we de ne the

Degree

thesis:*
Grantor dc:publisher
University of Ioannina
Year dc:date
2009

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Ιωαννίδου, Κυριακή
  • Ioannidou, Kyriaki

Subjects

dc:subject × 19

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/18620

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Ιωαννίδου, Κυριακή; Ioannidou, Kyriaki. Χαρακτηρισμός νέων κλάσεων τέλειων γραφημάτων και αγλόριθμοι χρωματισμού και μέγιστων διαδρομών. University of Ioannina, 2009. http://hdl.handle.net/10442/hedi/18620