This open problem is brought to you by:
5th International Combinatorics Conference (5ICC)
http://www.monash.edu/5icc
4-9 December 2017, Monash University, Melbourne, Australia.
Invited speakers include
Maria Chudnovsky,
David Eppstein,
Jacob Fox,
Daniela Kühn,
Alexander Scott,
Paul Seymour.
A graph
G is
k-colourable with defect d, or simply (
k,
d)-
colourable, if each vertex
v of G can be assigned one of
k colours so that at most d neighbours of
v are assigned the same colour as v. That is, each monochromatic subgraph has maximum degree at most
d. Let's focus on minimising the number of colours
k rather than the degree bound
d. This viewpoint motivates the following definition
[7]. The
defective chromatic number of a graph class
C is the minimum integer
k (if such a
k exists) for which there exists an integer
d such that every graph in
C is (
k,
d)-colourable.
Consider the following three examples: Archdeacon
[2] proved that for every surface
Σ, the defective chromatic number of graphs embeddable in
Σ equals 3. Edwards, Kang, Kim, Oum, and Seymour
[3] proved that the class of graphs containing no
K_{s+1} minor has defective chromatic number
s (which is a weakening of Hadwiger's conjecture). Ossona de Mendez, Oum, and Wood
[7] proved that for
s ≤
t, the class of graphs containing no
K^{*}_{s, t} minor has defective chromatic number
s (which implies the above two results). Ossona de Mendez, Oum, and Wood
[7] conjectured the following:
Conjecture [7]: For every connected graph
H, the defective chromatic number of
H-minor-free graphs equals the tree-depth of
H minus 1.
Here the
tree-depth of a connected graph
H is the minimum height of a rooted tree
T such that
H is a subgraph of the closure of
T. Here the
closure of
T is obtained from
T by adding an edge between every ancestor and descendent in
T. The
height of a rooted tree is the maximum number of vertices on a root-to-leaf path. The
tree-depth of a disconnected graph
H is the maximum tree-depth of the connected components of
H.
Ossona de Mendez et al.
[7] showed that the defective chromatic number of
H-minor-free graphs is at least the tree-depth of
H minus 1. The construction is from
[3]. Let
G(
s,
d) be the closure of the complete
d-ary tree of height
s. We prove by induction on
s that every (
s-1)-colouring of
G(
s,
d) has a vertex of monochromatic degree at least
d. In the base case, since
G(2,
d) is the star
K_{1, d}, every 1-colouring of
G(2,
d) has a vertex with monochromatic degree
d, as claimed. Consider an (
s-1)-colouring of
G(
s,
d). Let
v be the dominant vertex in
G(
s,
d). Say
v is coloured blue. Then
G(
s,
d)-
v consists of
d disjoint copies of
G(
s-1,
d). If some copy of
G(
s-1,
d) contains no blue vertex, then
G(
s-1,
d) is (
s-2)-coloured, and by induction contains a vertex with monochromatic degree at least
d, and we are done. Otherwise, each copy of
G(
s-1,
d) contains a blue vertex, in which case,
v has monochromatic degree at least
d.
Now, given a connected graph
H, let
s+1 be the tree-depth of
H. By definition,
G(
s,
d) has tree-depth
s. Since tree-depth is minor-monotone, every minor of
G(
s,
d) has tree-depth at most
s. Thus
H is not a minor of
G(
s,
d). As proved above, every (
s-1)-colouring of
G(
s,
d) has a vertex with monochromatic degree at least
d (which is unbounded). Thus the defective chromatic number of the class of
H-minor-free graphs is at least
s.
The conjecture is true for
H = K_{t} (
[3]), for
H = K_{s, t} or
H = K^{*}_{s, t} (
[7]), and for connected graphs with tree-depth at most 3 (
[7]). Mohar, Reed, and Wood
[6] proved that the defective chromatic number of the class of graphs with circumference
k (that is,
C_{k+1}-minor-free graphs) is at most 3 log
_{2} k, which is within a factor of 3 of the conjecture. This also provides the best known result when
H is a path.