Hide menu

Graph Theory

FDA156, 2003HT

Status Archive
School National Graduate School in Computer Science (CUGS)
Division LiU
Owner Jörgen Hansson

If you would like to register for this course, please contact Anne Moe, annes@ida.liu.se

  Log in  




Course plan

Lectures

30 hours of lectures and seminars

Recommended for

CUGS doctoral students, ECSEL students.

The course was last given

This is a new course

Goals

Prerequisites

Discrete structures II

Contents

- Matchings and factors: matching and covers, bipartite matching, matchings in general graphs
- Connectivity and paths: k-connected graphs, network flow problems
- Coloring of graphs: vertex colorings and upper bounds, structure of k-chromatic graphs, enumerative aspects
- Planar graphs: drawings in the plane, dual graphs, Kurtaoski's theorem, parameters of planarity
- Edges and cycles: Line graphs and edge-coloring, Hamiltonian cycles, planarity, coloring and cycles

Organization

30 hours of lectures and seminars. Course is given in condensed form.

Literature

Douglas B. West: Introduction to graph theory
second edition 2001, Prentice Hall, ISBN 0-13-014400-2

Lecturers

Leif Melkersson, MAI, LiU

Examiner

Leif Melkersson, MAI, LiU

Examination

To be determined

Credit

5 credits

Organized by

Department of Mathematics, Linköping university in collaboration with CUGS

Comments

The course is an intensive course consisting of 2-3 day sessions (usually 2-3 sessions) at the study centre/university. The course has no admission fee, but course participants (or the groups they belong to) pay for travel and any food and accomodation.(For students registered with CUGS, the research school will pay for food and accomodation.)

More information about this is available at http://www.ida.liu.se/cugs/


Page responsible: Director of Graduate Studies