Transcript slides

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
1st day
2nd day
3rd day
4th day
5th day
This is an edge colouring problem.
Each edge is a game.
Each day is a colour.
 ' ( K6 )  5
 ' ( K 2 n )  2n  1
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: 5 days
7 days are enough
7 days are needed
There are 7 colours
Each edge misses at most 2 colours
Edge list colouring
ch' ( K 6 )  5
Each edge has 5 permissible colours
I do not know any easy proof
List colouring conjecture:
For any graph G,
ch ' (G )   ' (G )
However, the conjecture remains open for K 2n
Haggkvist-Janssen (1997)
ch ' ( K n )  n
If n is odd, then ch'(K n )  n
Uwe Schauz (2014)
If p is a prime, n  p - 1, then ch'(K n )  n  1
A scheduling problem
There are six 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: 5 days
7 days are enough
The choices are made
before the scheduling
A scheduling problem
There are six teams, each needs to compete
with all the others.
Each team can play one game per day
is allowed
not day
to show
Each team can
choose one
off up for one day
How many days are needed to schedule
all the games?
On each day, we know
which teams haven’t shown up today
7 days are enough
but we do not know which teams
will not show up tomorrow
We need to schedule the games for today
On-line list colouring of graphs
We start colouring the graph
before having the full information of the list
f : V (G)  0,1,2,
f (x ) is the number of permissible colours for x
f-painting game (on-line list colouring game) on G
Each vertex v is given f(v) tokens.
Each token represents a permissible colour.
But we do not know yet what is the colour.
Two Players:
Lister
Reveals the list
Painter
Colours vertices
At round i
Lister choose a set Vi of uncoloured vertices, removes
one token from each vertex of Vi
Vi is the set of vertices which has colour i as
a permissible colour.
Painter chooses an independent subset I i of Vi
vertices in I i are coloured by colour i.
If at the end of some round, there is an uncolored
vertex with no tokens left, then Lister wins.
If all vertices are coloured then
Painter wins the game.
G is f-paintable if Painter has a winning strategy for
the f-painting game.
G is k-paintable if G is f-paintable for
f(x)=k for every x.
The paint number ch p(G ) of G is the
minimum k for which G is k-paintable.
On-line
List colouring:
list colouring:
Painter start colouring the graph
after having the full information of the list
before
choice number
ch(G)  min k : G is k - choosable 
ch p(G )  ch(G )
 2, 2, 4
is not 2-paintable
 2, 2, 4
Theorem [Erdos-Rubin-Taylor (1979)]
 2, 2, 2 n
is 2-choosable.
 2, 2, 4
is not 2-paintable
 2, 2, 4
Lister wins the game
3
4
5
3
5
1
4
2
3
2
1
Theorem [Erdos-Rubin-Taylor,1979]
A connected graph G is 2-choosable if and only if its core is
K1
or
C 2n
or
 2,2,2 p
However, if p>1, then  2,2,2 p is not 2-paintable.
Theorem [Zhu,2009]
A connected graph G is 2-paintable if and only if its core is
K1
or
C 2n
or
 2,2,2
Problems studied
Planar graphs and locally planar graphs
Chromatic-paintable graphs
Complete bipartite graphs
Random graphs
Partial painting game
b-tuple painting game and fractional paint number
Defective painting game
Sum-painting number of graphs
Methods:
1. Derandomize probability arguments
2. Polynomial method
3. Inductive proof
4. Kernel method
5. Probability
Complete bipartite graphs
Theorem [Erdos,1964]
If G is bipartite and has n vertices , then
ch(G)  log 2 n  1
Theorem[Zhu,2009]
If G is bipartite and has n vertices, then
chp(G )  log2 n  1
probabilistic proof
A
B
Probability proof:
Each color is assigned to vertices in A or B with probability
Initially, each vertex x has weight w(x)=1
A
Assume Lister has given set
If
Vi
B
w( A  Vi )  w( B  Vi )
Painter colours A  Vi ,
double the weight of each vertex in
B  Vi
A
The total weight of uncoloured vertices
is not increased.
B
If a vertex is given a permissible colour but is not coloured
by that colour, then its weight doubles.
If x has been given k permissible colours, but remains uncoloured,
then
ww((xx))22kk  n
k  log 2 n
If x has log 2 n  1 permissible colours, Painter will be
able to colour it.
Initially, each vertex x has weight w(x)=1
A
Assume Lister has given set
Vi
B
If
w( A  Vi )  w( B  Vi )
Painter colours A  Vi ,
double the weight of each vertex in
B  Vi
ch(K n ,n ) and chp(K n ,n )
Theorem
Erdos-Lovasz
[RadhaKrishnan-Srinivasan,2000]
Conjecture
Theorem
[Erdos,
1964]
1
2
o(1))
log2 log2 n
ch(K n ,n ) 
 log 2 n 
(o11(1)log
2 n
ch(K n ,n ) and chp(K n ,n )
Theorem
Erdos-Lovasz
[RadhaKrishnan-Srinivasan,2000]
Conjecture
Theorem
[Erdos,
1964]
1
2
o(1))
log2 log2 n
ch(K n ,n ) 
 log 2 n 
(o11(1)log
2 n
The proof uses a probability argument.
The argument CANNOT be derandomized to give a
strategy for the painting game.
ch(K n ,n ) and chp(K n ,n )
Theorem
Erdos-Lovasz
[RadhaKrishnan-Srinivasan,2000]
Conjecture
Theorem
[Erdos,
1964]
1
2
o(1))
log2 log2 n
ch(K n ,n ) 
 log 2 n 
(o11(1)log
2 n
Theorem [Duray-Gutowski-Kozik,2015]
chp(K n ,n )  log2 n  O(1)
Corollary
chp K n ,n   ch K n ,n   log2 log2 n 
Some other results proved by derandomizing probabilistic arguments
1: Partial online list colouring
Partial painting game
Partial f-painting game on G
same as the f-painting game, except that Painter’s goal
is not to colour all the vertices, but
to colour as many vertices as possible.
Fact:
If (G )  k , then using k' k colours, one can
colour at least
k'
V
k
vertices.
Conjecture [Albertson]:
If ch(G )  k , each vertex has k' k permissible
colours, one can colour at least
k'
V
k
vertices.
Conjecture [Zhu, 2009]:
If ch P(G )  k , each vertex has k' k tokens
then Painter has a strategy to colour at least
k'
V
k
vertices.
Conjecture
Theorem
[Wong-Zhu,2013]
[Zhu, 2009]:
If ch P(G )  k , each vertex has k' k tokens
then Painter has a strategy to colour at least
6 k'
vertices.
V
7 k
Proof: Derandomize a probabilistic argument
Some other results proved by derandomizing probabilistic arguments
1: Partial online list colouring
2. Fractional online choice number
b-tuple list colouring
G is (a,b)-choosable
if |L(v)|=a for each vertex v, then there is a b-tuple
L-colouring.
b-tuple on-line list colouring
If each vertex has a tokens, then Painter has a
strategy to colour each vertex a set of b colours.
a

f (G )  inf : G is (a,b) - colourable
b

a

chf (G )  inf : G is (a,b) - choosable
b

a

chp(G )  inf : G is (a,b) - paintable
b

Theorem [Alon-Tuza-Voigt, 1997]
f (G )  chf (G )
Infimum attained
Probabilistic arguemnt
[Gutowski, 2011]
f (G )  chP(G )
Infimum not attained
Methods:
1. Derandomize probability arguments
2. Polynomial method
paintable
= deg(P(G))
Some results proved by using polynomial method
Haggkvist-Janssen (1997)
ch'p'(( K
K n )) nn
If n is odd, then ch''p(K
(Knn))  nn
Uwe Schauz (2014)
If n  p  1,p is an odd prime, then ch
ch'p(K
'(Knn))  nn  11
Methods:
1. Derandomize probability arguments
2. Polynomial method
3. Inductive proof
A recursive definition of f-paintable
Assume f : V (G)  0,1,2, . Then G is f-paintable, if
(1) V (G )  
or
X  V (G ),  independent set I
(2)
G-I is (f-δX )  paintable.
 X : characteristic function of X
 X,
Upper bounds for ch(G) proved by induction
Planar graphs
[ Schauz,2009
] Every planar graph is 5-choosable
Theorem [Thomassen,
1995]
paintable
G embedded in a surface 
non-contractible
edge-width of G
length of shortest
non-contractible cycle
contractible
Locally planar
edge-width is large
： torus
Theorem [Thomassen, 1993] For any surface  , there is a
constant w , any G embedded in  with edge-width > w
is 5-colourable.
G embedded in a surface 
non-contractible
edge-width of G
length of shortest
non-contractible cycle
contractible
Locally planar
edge-width is large
： torus
Han-Zhu
DeVos-Kawarabayashi-Mohor
2015
2008
Theorem [Thomassen,
1993] For any surface  , there is a
constant w , any G embedded in  with edge-width > w
is 5-colourable.
choosable
paintable
Chromatic-paintable graphs
A graph G is chromatic choosable
paintable if ch
chp((GG)) (G(G) )
Conjecture: Line graphs are chromatic choosable.
paintable
Conjecture: Claw-free graphs are chromatic choosable.
paintable
Conjecture: Total graphs are chromatic choosable.
paintable
[Kim-Park,2013]
Conjecture: Graph squares are chromatic choosable.
Theorem
Ohba Conjecture: Graphs G with | V (G ) | 2  (G )  1
[Noel-Reed-Wu,2013] are chromatic choosable.
paintable
A graph G is chromatic choosable
paintable if ch
chp((GG)) (G(G) )
Conjecture: Line graphs are chromatic choosable.
paintable
Conjecture: Claw-free graphs are chromatic choosable.
paintable
Conjecture: Total graphs are chromatic choosable.
paintable
[Kim-Park,2013]
Conjecture: Graph squares are chromatic choosable.
Ohba
Conjecture: Graphs G with | V (G ) | 2  (G )  1 NO!
Question
are chromatic choosable.
paintable
Theorem [Kim-Kwon-Liu-Zhu,2012]
For k>1,
K 2k ,3 is not (k+1)-paintable.
K 2, 2,3 is not 3-paintable.
On-line version
Huang-Wong-Zhu 2011
Ohba Conjecture: Graphs G with | V (G ) | 2  (G )  1
are chromatic choosable.
paintable
To prove this conjecture, we only need to consider
complete multipartite graphs.
Theorem [Kozik-Micek-Zhu,2014]
On-line Ohba conjecture is true for graphs
with independence number at most 3.
The key in proving this theorem is to find a “good”
technical statement that can be proved by induction.
ordered
parts of size 1
parts of size 2
parts of size 3
parts of size 1 or 2
ordered
Partition of the parts
into four classes
A1
A2
ordered
parts of size 1
parts of size 2
parts of size 3
A k1
k2
k3
Bi
Ci
S1
parts of size 1 or 2
ordered
S2
Ss
vS (i ) 
| S
1 j i
j
|
For Ai  v
f (v )  k 2  k 3  i
For Bi  u, v
f (v)  k2  k3
G is f-paintable
f (v)  f (u ) | V (G ) |
For Ci  u, v, w
f (v)  k2  k3
f (v)  f (u ) | V (G ) | 1
f (v)  f (u)  f (w) | V (G) | 1  k1  k2  k3
For v  Si
f (v)  k1  k2  2k3  vS (i)
Theorem [Kozik-Micek-Zhu,2014]
On-line Ohba conjecture is true for graphs
with independence number at most 3.
Theorem [Chang-Chen-Guo-Huang,2014+]
m2  m  2
If (G )  m , | V | 2
(G )
m  3m  4
then G is chromatic - paintable
(g )  4,| V |
7
(G )    paintable
4
d-defective painting game
At round i
Lister choose a set Vi of uncoloured vertices, removes
one token from each vertex of Vi
Vi is the set of vertices which has colour i as
a permissible colour.
I i of V
Painter chooses
chooses aansubset
independent
I i of Vsubset
iG[I i ]  d
Painter
i such that
vertices in I i are coloured by colour i.
Questions
Theorem [
,
,1999]
Planar graphs are 2-defect 3-choosable.
paintable ?
No!
Gutowski-Han-Krawczyk-Zhu, 2016
paintable ?
Yes!
Han-Zhu, 2015
Theorem [Cushing-Kierstead,2010]
Planar graphs are 1-defect 4-choosable.
paintable ?
Open
Han-Zhu 2015
Locally planar graphs are 2-defective 4-paintable.
Methods:
1. Derandomize probability arguments
2. Polynomial method
3. Inductive proof
4. Kernel method
Let D be an orientation of G.
A kernel in D is an independent set I for which
every vertex not in I has an out-neighbour in I
D
I
A directed graph D is kernel perfect
if every induced sub-digraph has a kernel.
Theorem
If G has an orientation D which is kernel perfect,
then G is (d D  1)  paintable
An example:
Theorem [Galvin,1995] If G is bipartite, then  'p (G )  (G )
Methods:
1. Derandomize probability arguments
2. Polynomial method
3. Inductive proof
4. Kernel method
5. Probability
Theorem [Frieze, Mitsche,Perez-Gimenez, Pralat, 2015]
Theorem [Frieze, Mitsche,Perez-Gimenez, Pralat, 2015]
At each round, if Lister presents a large set M,
then we are sure that M contains a large independent set I.
Painter colours I.
If Lister presents a small set M, then Painter randomly colours
one vertex from the set.
Nine Dragon Tree
Thank you
Lister
33
33
333
Lister
33
33
333
Painter
3
23
233
23
23
33
Lister
33
33
333
Painter
3
23
233
23
23
33
Lister
Lister
33
33
333
Painter
3
23
233
23
23
33
Lister
Lister
33
33
333
Painter
3
23
233
23
23
33
Lister
Painter
13
222
2
3
222
3
13
22
Lister
33
33
333
Painter
3
23
233
23
23
33
Lister
Painter
13
222
2
3
222
3
13
22
Lister
Lister
33
33
333
K 2, 2,3
is not 3-paintable
Painter
3
23
233
23
23
33
Lister
Painter
13
222
2
3
222
3
13
22
Lister
Painter Lose
3 {123}
111
{1}{2}{3}
2
112
Painter Lose
2
3
11
Painter Lose
Theorem [Huang-Wong-Zhu,2011]
K 2k
is k-paintable
paintable
= deg(P(G))
Theorem [Huang-Wong-Zhu,2011]
K 2k
is k-paintable
Theorem [Mahoney, Tomlinson Wise, 2014]
If G is an outerplanar graph whose weak dual is a path,
then G is online sum choice greedy.
Conjecture [Mahoney, Tolinson, Wise]
Every outerplanar graph is online sum choice greedy.