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