Top

Published in:

2017 | OriginalPaper | Chapter

3. Perfect Graphs and Comparability Graphs

Author : Remigiusz Wiśniewski

Published in: Prototyping of Concurrent Control Systems Implemented in FPGA Devices

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The first use of graph theory is dated to 1735. Swiss mathematician and physicist, Leonhard Euler, formulated theorems and definitions related to graphs. Euler was inspired by a real problem regarding crossing bridges in Königsberg (east Prussia, also known as Królewiec, Kaliningrad). He tried to take a walk around the city in such a way that each of the seven bridges was crossed only once. Finally, Euler proved that it was impossible, simultaneously solving the puzzles with the application of graph theory. Nowadays, such a theory is used in numerous fields of science and practical approaches. This chapter presents notations and definitions related to the graph theory. Furthermore, perfect graphs and comparability graphs are introduced. New theorems, lemmas, and algorithms regarding recognition and coloring of comparability graphs are proposed.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Related Work

next chapter Hypergraphs and Exact Transversals

Aho AV, Hopcroft JE, Ullman J (1983) Data structures and algorithms, 1st edn. Addison-Wesley Longman Publishing Co. Inc, BostonMATH

Bang-Jensen J, Gutin GZ (2007) Digraphs: theory, algorithms and applications, 1st edn. Springer, IncorporatedMATH

Berge C (1973) Graphs and hypergraphs. North-Holland Pub. Co.; American Elsevier Pub. Co., Amsterdam, New YorkMATH

Bron C, Kerbosch J (1973) Algorithm 457: finding all cliques of an undirected graph. Commun ACM 16(9):575–577CrossRefMATH

Chandler D, Chang M-S, Kloks T, Liu J, Peng S-L (2006) Partitioned probe comparability graphs. In: Fomin F (ed) Graph-theoretic concepts in computer science, vol 4271., Lecture notes in computer scienceSpringer, Heidelberg, pp 179–190CrossRef

Corno F, Prinetto P, Sonza Reorda M (1995) Using symbolic techniques to find the maximum clique in very large sparse graphs. In: EDTC ’95: Proceedings of the 1995 European conference on design and test, Washington, DC, USA, 1995. IEEE Computer Society, p 320

Cornuéjols G, Liu X, Vuskovic K (2003) A polynomial algorithm for recognizing perfect graphs. In: FOCS. IEEE Computer Society Press, pp 20–27

Diestel R (2000) Graph theory. Springer, New York (Electronic Edition)

Golumbic MC (1977) The complexity of comparability graph recognition and coloring. Computing 18(3):199–208MathSciNetCrossRefMATH

10.

Golumbic MC (1980) Algorithmic graph theory and perfect graphs

11.

Grötschel M, Lovász L, Schrijver A (1984) Polynomial algorithms for perfect graphs. Perfect graphs, volume 21 of Annals of Discrete Mathematics. North-Holland, Amsterdam, pp 325–356

12.

Habib M, McConnell R, Paul C, Viennot L (2000) Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoret Comput Sci 234(1–2):59–84MathSciNetCrossRefMATH

13.

Harary F (1994) Graph theory. Addison-Wesley, ReadingMATH

14.

Homer S, Selman A (2001) Computability and complexity theory. In: Texts in computer science. Springer

15.

Jensen TR, Toft B (1995) Graph coloring problems. Wiley-Interscience, New YorkMATH

16.

Johnson DS, Papadimitriou CH, Yannakakis M (1988) On generating all maximal independent sets. Inf Process Lett 27(3):119–123MathSciNetCrossRefMATH

17.

Kelly D (1985) Comparability graphs. In: Rival I (ed) Graphs and order, vol 147., NATO ASI seriesSpringer, Netherlands, pp 3–40CrossRef

18.

Kubale M (2004) Graph colorings. American Mathematical Society

19.

Lovász L (1972) Normal hypergraphs and the weak perfect graph conjecture. Discrete Math 2:253–267MathSciNetCrossRefMATH

20.

Lovász L (1983) Perfect graphs. In: Beineke L, Wilson R (eds) Selected topics in graph theory, vol 2. Academic Press

21.

Makino K, Uno T (2004) New algorithms for enumerating all maximal cliques. In: Hagerup T, Katajainen J (eds) Algorithm theory—SWAT 2004, vol 3111., Lecture notes in computer scienceSpringer, Heidelberg, pp 260–272CrossRef

22.

Shamir R (1994) Advanced topics in graph algorithms

23.

Tomita E, Tanaka A, Takahashi H (2006) The worst-case time complexity for generating all maximal cliques and computational experiments. Theoret Comput Sci 363(1):28–42MathSciNetCrossRefMATH

24.

West DB (2000) Introduction to graph theory, 2nd edn. Prentice Hall

Title: Perfect Graphs and Comparability Graphs
Author: Remigiusz Wiśniewski
Publisher: Springer International Publishing
Book: Prototyping of Concurrent Control Systems Implemented in FPGA Devices
Print ISBN: 978-3-319-45810-6

Electronic ISBN: 978-3-319-45811-3

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-45811-3_3