HS2024: 53085 Graph Theory and Applications

In this course, we first introduce some basic concepts and notions of graph theory. We then present a series of graph theoretical problems with real world applications. Some of them are, unfortunately, hard to solve in general. Hence, in the rest of the course, we focus on solving these problems efficiently on classes of graphs that enjoy specific structural properties.

General Information

Course description

In this course, we first introduce some basic concepts and notions of graph theory. We then present a series of graph theoretical problems and invariants with real world applications. Some of them are, unfortunately, hard to compute in general. Hence, in the rest of the course, we focus on solving these problems efficiently on classes of graphs that enjoy specific structural properties.

Syllabus

1. Introduction: basic notions and definitions

2. Some classic invariants: independence number (α), clique number (ω), vertex cover number (τ), matching number (ν), chromatic number (χ), and chromatic index (χ′)
• Definitions and overview
• Relations between invariants
• Distinguish their computational complexity on general graphs
• Real-life motivations
• Bounds and relations on the corresponding invariants on general graphs

3. Some restricted graph classes [most lectures will be part of this chapter]
• Bipartite graphs
• Chordal graphs and subclasses
• Planar graphs

General

Language

English

Availability

Access

Unlimited

Admittance

You can join this course directly.

Registration Period

Unlimited

Personal Data Visible to Course Administrators

Data Types of the Personal Profile

Username
First Name
Last Name
E-Mail