浙江师范大学：On-line list colouring of graphs

On-line list colouring of graphs Xuding zhu Zhejiang Normal University 2016.8.23 CAM Hongkong

On-line list colouring of graphs Xuding Zhu Zhejiang Normal University 2016.8.23 CAM Hongkong

A scheduling problem There are six basketball teams, each needs to compete with all the others Each team can play one game per day How many days are needed to schedule all the games Answer: 5 days

There are six basketball teams, each needs to compete with all the others. Each team can play one game per day How many days are needed to schedule all the games? Answer: 5 days A scheduling problem:

I st day

1st day

2nd day

2nd day

Brd day y

3rd day

4th day

4th day

5th day

5th day

This is an edge colouring problem Each edge Is a game Each day is a colour x(K6)=5 x'(K2n)=2n-1

'(K6 ) = 5 '(K2n ) = 2n −1 This is an edge colouring problem. Each day is a colour. Each edge is a game

A scheduling problem There are six basketball teams. each needs to compete with all the others Each team can play one game per day Each team can choose one day off How many days are needed to schedule all the games? Answer days 7 days are needed 7 days are enough

There are six basketball teams, each needs to compete with all the others. Each team can play one game per day How many days are needed to schedule all the games? Answer: 5 days Each team can choose one day off 7 days are enough A scheduling problem: 7 days are needed

There are 7 colours Edge list colouring Each edge misses at most 2 colours ch(k6)=5 Each edge has 5 permissible colours I do not know any easy proof

Each edge misses at most 2 colours There are 7 colours Each edge has 5 permissible colours ch'(K6 ) = 5 I do not know any easy proof Edge list colouring