Role colouring graphs in hereditary classes
Christopher Purcell Puck Rombach


Two-particle indistinguishability and identification of boson-and-fermion species: A Fisher information approach




    Su-Yong Lee Jeongho Bang Jaewan Kim
    Received: date / Accepted: date
====================================================================================================================








    We study the computational complexity of computing role colourings
    of graphs in hereditary classes. We are interested in 
    describing the family of hereditary classes on which a role colouring with k colours can be 
    computed
    in polynomial time.
    In particular, we wish to describe
    the boundary
    between the “hard” and “easy” classes. The notion of a boundary class has been
    introduced by Alekseev in order to study such boundaries. Our main results are
    a boundary class for the k-role colouring problem and the related
    k-coupon colouring problem which has recently received a lot of attention in 
    the literature. The latter result makes use of a technique
    for generating regular graphs of arbitrary girth which may be of independent 
    interest.








§ INTRODUCTION





A role colouring of a graph G is an assignment r of colours to its vertices such that
if r(u)=r(v) then the image r(N(u)) of the neighbourhood of u is identical to the 
image r(N(v)) of the neighbourhood of v. The concept arises from the study 
of roles in a social network <cit.>, and has appeared in the literature
under the names role assignment <cit.> and regular equivalence <cit.>
and similar names <cit.>.

In a recent paper <cit.>, the present authors proved that the problem of deciding the existence of a role colouring with k colours (k-rcol) is -complete even when the input is restricted to planar graphs. This result is best possible, in the sense that if P is a minor-closed class of graphs, restricting k-rcol to graphs in P yields a polynomial time solution if and only if at least one planar graph is not in P. This is because planar graphs are the unique minimal minor-closed class of graphs of unbounded treewidth, and k-role colouring 
can be solved efficiently for bounded treewidth classes.

Our current focus is hereditary classes, where such classifications are not usually possible. Unlike the minor-closed case, hereditary classes are not well founded with respect to the containment relation; there need not be a minimal element in a set of hereditary classes. In order to overcome this difficulty, the concept of a boundary class was introduced by Alekseev <cit.> for the maximum independent set problem. For a problem Π we denote the family
of graph classes on which Π has a polynomial-time solution by Π-easy.
The importance of the notion of a boundary class is due to the following.
If X is defined by finitely many minimal forbidden induced subgraphs,
then X is outside Π-easy if and only if X contains a boundary class
for the family Π-easy (under the assumption that ≠).
One of our two main results is the first boundary class for k-rcol.

We also consider the special case of a coupon colouring.
A colouring of a graph G is a coupon colouring if every vertex
has a neighbour of every colour.
Coupon colourings are also known as total domatic partitions, and have recently received attention from the combinatorial <cit.>
and algorithmic <cit.> communities.
We will denote the problem of deciding the existence of a k-coupon colouring 
by k-ccol.
We give the first boundary class for this problem. 
Our proof makes use of a technique for constructing regular graphs
of arbitrary girth which may be of independent interest.
Explicit constructions for regular graphs of large girth have been known for a long time <cit.>. Our construction is far from extremal, but is meant to increase the girth of graphs while preserving k-coupon colourability.

In addition to the main results, we show that every non-trivial 2K_2-free
graph has a 2-role colouring and that this colouring can be found
in polynomial time. This is in contrast with the fact that the
problem is known to be -hard in this class for k≥ 4.

The rest of this paper is organised as follows. In the next section we give some definitions and preliminary discussion including a description of boundary classes. For a more thorough overview we direct the reader to <cit.>. The boundary classes for k-role colouring
and k-coupon colouring are given in Section 3 and Section 4 respectively. We conclude the paper
with a discussion of the possibility of other boundary classes and some open problems.



§ PRELIMINARIES


In this paper graphs may have loops but not multiple edges. Edges are undirected.
The neighbourhood of a vertex N_G(v) is the set of vertices that share an edge with v in G. This may include v if {v}∈ E(G). 
The degree of v is d(v)=|N_G(v)|. The minimum degree of all the vertices in G is denoted δ(G); the maximum is denoted Δ(G).




As usual, P_n,C_n and K_n denote the path, cycle and clique on n vertices respectively, and K_m,n denotes
the biclique on m+n vertices. 
The graphs P_n and C_n will be particularly important, and it will be useful to define
a consistent ordering of their vertices.
Let V(P_n)={ 1,2,…,n } and let E(P_n)={{1,2}, {2,3}, …, {n-1,n}}.
Let V(C_n)=V(P_n) and let E(C_n)=E(P_n)∪{{n,1}}. We define two more important
graphs similarly. Let P_n^* be the graph with V(P_n^*)=V(P_n),E(P_n^*)=E(P_n)∪{{n}}.
Let P_n^** be the graph with V(P_n^*)=V(P_n),E(P_n^*)=E(P_n)∪{{1},{n}}.

Let H be the graph on the left of Figure <ref>, and let u,v be the vertices
of H of degree 3. We define the graph H_i
to be the graph obtained from H by subdividing the edge {u,v} i-1 times.
Let S_ijk be the tree with 3 leaves at distance i,j, and k respectively 
from the single vertex of degree 3, for i,j,k≥ 1. If one of i,j or k is 
0, then let S_ijk=P_i+j+k+1. Figure <ref> shows S_ijk to the right.
An ear of a graph is a set of vertices of degree 2 that induces a path.




A set of graphs is called a class if it is closed under isomorphism. 
If a class is also closed under deleting vertices, we say that the class is hereditary. 
If a hereditary class is closed under deleting edges we say that it is a monotone class. 
A monotone class which is closed under edge contraction is said to be minor-closed. 
This paper mainly deals with hereditary classes. It is well known (and easy to verify) that a hereditary class can be characterised by its minimal forbidden induced subgraphs. For a set of graphs M, we say that a graph G is M-free if no graph in M is an induced subgraph of G. The class of M-free graphs will be denoted by Free(M). It will be useful to refer to the monotone class of graphs that contain no element of M as a subgraph (not necessarily induced) as Free_m(M).
Let  be a family of hereditary classes closed under taking subclasses. 
Suppose Y_1 ⊇ Y_2 ⊇… is an infinite sequence of graphs
outside  and let Y be their intersection. We say that Y is a limit class for ,
and a minimal limit class is a boundary class. A finitely defined graph class X is outside
 if and only if it contains none of the boundary classes for . 





A role colouring r:V(G) →ℕ^+ of a graph G is an assignment of colours to its vertices, such that if r(u)=r(v) then { r(u') : u' ∈ N(u)} = {r(v') : v' ∈ N(v)}. In other words, two vertices with the same colour have identical sets of colours in their respective neighbourhoods. 
For a role colouring r we define the role graph R to be the graph whose
vertex set is {i: ∃ v∈ V(G) r(v)=i} and an edge {x,y} if 
a vertex of colour x has a neighbour of colour y.
Formally, a role colouring r of a graph G with role
graph R is a locally surjective homomorphism from G to R.
We consider only finite role graphs.
If R has k vertices, we say that r has k colours
and is a k-role colouring.
We may identify the colours of r and the vertices of R,
and without loss of generality, these are {1,…,k}.
In particular, if R∈{C_k,P_k,P_k^*,P_k^**} then
the colours of r are ordered according to the definition
given above.
We refer to the problem of deciding the existence of a k-role colouring for a graph G as k-rcol, and the problem of deciding the existence of a role-colouring with role graph R for a graph G as R-rcol.



If G is a connected graph with a role colouring r, then the role graph R of the colouring is connected.



If G has a non trivial role colouring r with a connected role graph R then N[v] is not monochromatic for any vertex v.


A CNF formula ϕ is a disjunction of clauses C_1 ∧…∧ C_m,
each of which is a conjunction of literals C_i = l_1 ∨…∨ l_j, each of which
is a variable (or its negation) that takes a value T or F. A formula
is monotone if every literal is a variable (and not a negation of a variable).
A not-all-equal satisfying assignment of ϕ is a satisfying assignment of T,F to 
its variables so that each clause has at least one literal whose value is F. The problem of deciding whether a (monotone)
formula has a not-all-equal satisfying assignment is denoted by (monotone) nae-sat.
This problem is known to be -complete <cit.>.



§ ROLE COLOURINGS




Let S_j be the class of (K_1,4,C_3,…,C_j,H_1,…,H_j)-free graphs and let =∩_j^∞ S_j. In this section we prove the following theorem.


For all k≥ 2,  is a boundary class for the k-rcol problem.




 §.§ The limit class


In order to prove Theorem <ref>, we first consider the complexity of the P_k^**-rcol problem. We need the following lemma.





Let G be a graph and let (H,p) be in {(C_k,k),(P_k,2k-2),(P_k^*,2k-1),(P_k^**,2k)}. Let {x,y_1,…,y_p-1,z} be a path in G such that the degree of y_i is 2 for all i.
Then if G has a valid H-role-colouring r, we have that r(x)=r(z).




We give the proof for the case (H,p)=(P_k^**,2k), the other cases
are analogous. Let r be a P_k^**-role colouring of G.
Consider a walk in P_k^** that never uses the same edge twice in a row. It is easy to see that after 2k steps, the walk will return to the initial vertex.
Observe that the colours r(x),r(y_1),…,r(y_2k-1),r(z) describe such a walk: the two neighbours of y_i must have different colours. Since this walk is 2k steps, we have that r(x)=r(z).







For all k≥ 2, the P_k^**-rcol problem is hard for graphs of vertex degree at most 3.



We reduce from monotone nae-sat. Let ϕ be a boolean formula
such that each of its variables appears positively. We will construct a graph G_ϕ such that ϕ has a not-all-equal satisfying assignment if and only if G_ϕ has a P_k^**-role-colouring. Furthermore, G_ϕ will have vertex degree at most 3.



Suppose ϕ has n variables x_1,…,x_n and that x_i appears s_i times in ϕ (in some arbitrary order). For each variable x_i we include in G_ϕ a cycle { x_i^1,…, x_i^2k(s_i +1)}.
The vertex set of G_ϕ will also include the clauses of ϕ, in some arbitrary order {C_1,C_2,…}. Suppose x_i appears for the pth time in clause C_q. Then we add an edge connecting x_i^2pk+2 and C_q. We will refer to this part of the graph as the formula gadget.

Additionally, we add a cycle of length 2kn. We denote this cycle by { v_i^j } with 1 ≤ i ≤ n,1≤ j ≤ 2k. 
For each x_i we add a path {w_i^1,… w_i^2k-1} and edges v_i^1 w_i^1 and w_i^2k-1 x_i^1. This completes the description of G_ϕ.

We now argue that G_ϕ has a P_k^**-role-colouring if and only if ϕ has a not-all-equal satisfying assignment. Suppose first that G_ϕ has such a colouring, r. We will say that a set of vertices X is monochromatic if every vertex in X has the same colour. Observe that by Lemma <ref> the set {v_i^1: 1 ≤ i ≤ n }∪{x_i^1: 1 ≤ i ≤ n } is monochromatic; let the colour of the vertices in this set be c. For each i there are two choices for the colour of x_i^2, we call them c_t and c_f (which need not be distinct from c). Observe that, for each i, we have that {x_i^2pk+2: 0 ≤ p ≤ s_i } is monochromatic with colour c_t or c_f.

For each clause vertex C_q there are three cases to consider, since these vertices only have neighbours in the sets {x_i^2pk+2: 0 ≤ p ≤ s_i }. In the first two cases, the neighbourhood of C_q is monochromatic with colour c_t or c_f. This is a contradiction since there is no colour that has degree 1 in P_k^**. In the remaining case, C_q has at least one neighbour of colour c_t and at least one neighbour of colour c_f, and r(C_q)=c. Now we can obtain a not-all-equal satisfying assignment for ϕ. Those variables x_i for which  {x_i^2pk+2: 0 ≤ p ≤ s_i } has colour c_b can be assigned the truth value b∈{t,f}. Clearly, each clause has at least one variable assigned 0 and at least one variable assigned 1 in this case.

It remains for us to show that a P_k^**-role-colouring for G_ϕ can be constructed from a not-all-equal satisfying assignment for ϕ. 
Given such an assignment we construct a colouring r as follows. For any vertex w in {x_i^1: 1 ≤ i ≤ n}∪{v_i^1: 1 ≤ i ≤ n }∪{C_1,C_2,…} we set r(w)=1.
Observe that this does not contradict the condition given by Lemma <ref>. 
Since the variable gadget for x_i is a cycle of length a multiple of 2k, 
we can colour its vertices with colours 1,1,2,3,4,…,k-1,k,k,k-1,…,3,2 repeated s_i times, 
in one of two possible directions. If x_i is assigned t, then we set r(x_i^2)=1,r(x_i^3)=2 and so on. 
Otherwise we set r(x_i^2)=2,r(x_i^3)=3 and so on. 
Observe that each vertex in the set {x_i^2pk+2: 0 ≤ p ≤ s_i } has colour 1 if x_i is assigned t and with colour 2 otherwise. By colouring the clause vertices with colour 1, we have that the colouring is valid for all vertices of the formula gadget.

The cycle in the base gadget is also of length a multiple of 2k, so we can colour it with colours 1,1,2,3,…,k-1,k,k,k-1,…,3,2 repeated n times. We restate that r(v_i^1)=1 for all i. We complete the colouring by giving the vertices w_i^1,w_i^2,…,w_i^2k-1 the colours 2,3,…,k-1,k,k,k-1,…,3,2,1 respectively, for all i. Since w_i^1 has a neighbour v_i^1 of colour 1, and w_i^2k-1 has a neighbour x_i^1 of colour 1, we see that the colouring is valid for all vertices of the base gadget. This completes the proof. We illustrate this construction in Figure <ref>, for the boolean formula Φ= (x ∨ y) ∧ (y ∨ z), with k=3 and role graph P_3^**.




The graph G_ϕ may have a k-role-colouring with a role graph different to P_k^**. In particular, there exists a formula ϕ with no not-all-equal satisfying assignment that is k-role colourable. Thus our construction does not immediately prove that k-role-colouring is hard for graphs of vertex degree at most 3. We now show how to overcome this difficulty by modifying G_ϕ to fix the role graph. 

Let H be an induced subgraph of G such that exactly one vertex v in V(H) has exactly one neighbour in V(G)∖ V(H), while all other vertices of H have no neighbours in V(G)∖ V(H). We say that H is a dangling induced subgraph of G, and that v is the hook of H.


Let r be a role colouring of a graph G, with role graph R. Then the degree of r(v) in R is
at most the degree of v in G. Furthermore,
δ(G) ≤δ (R) ≤Δ(R) ≤Δ(G).






Let G have an ear of length at least 2k and suppose G is k-role-colourable with connected role graph R. Then R∈{C_k,P_k,P_k^*,P_k^**}.




Suppose the contrary. Then there must be a colour c_1 in R of degree at least 3. 
Let v_1,…,v_2k be the vertices of an ear. By Observation <ref>,
no vertex of the ear has colour c_1. 
For some j, assume that no vertex in v_i with j+1 ≤ i ≤ 2k-j
has a colour of distance at most j from c_1 in R.
If there is no colour of distance j+1 from c_1 in R then
we have reached a contradiction.
Otherwise, let c' be such a colour, and observe that 
if a vertex v_i with j+2 ≤ i ≤ 2k-j-1 has colour c'
then c' has degree 2 in R, and one of the two neighbours 
of v_i necessarily has a colour of distance j from R,
a contradiction.
By induction, we see that r(v_k+1) is at distance
strictly more than k from c_1, which gives a contradiction
that completes the proof.







Let G be a graph with a dangling induced subgraph H isomorphic to C_2k-1,
and suppose that G is k-role-colourable with connected role graph R. Then R∈{P_k^*,P_k^**}.





Let V(H)={v_1,…,v_p(k)} and let v_1 be the hook of H. 
By Lemma <ref>, R∈{C_k,P_k,P_k^*,P_k^**}. 
Clearly there is no way to colour the vertices of H such
that the role colouring is a C_2k.
By Lemma <ref>,
if R=P_k, then v_1 and v_p(k) have the same colour, which
is a contradiction. Figure <ref> illustrates two copies of H for k=3, one that is P_3^*-role coloured, and one that is P_3^**-role coloured.









Let p(k) as before. Let G be a graph with two dangling induced subgraphs H,H',
each isomorphic to C_2k, with respective hooks v_1,v'_1. Let u be the unique neighbour of v_1 in V(G)∖ V(H) and let u' be the unique neighbour of v'_1
in V(G)∖ V(H'). Let u and u' be adjacent in G. Suppose r is a k-role-colouring of G with connected role graph R. Then R∈{C_k,P_k,P_k^**}






Let V(H)={v_1,…,v_p(k)} and V(H')={v'_1,…,v'_2k}. By Lemma <ref>, R ∈{C_k,P_k,P_k^*,P_k^**}. By Lemma <ref>, if R=P_k^* then v_1 and v_p(k) have the same colour; i.e., they have colour k. Similarly,
v_2 has colour k. For the same reason, v'_1,v'_2 and v'_2k have colour k.
Since r is a P_k^*-colouring, v_1 must have a neighbour of colour k-1. 
We must have that r(u)=k-1 and symmetrically, r(u')=k-1, which gives a contradiction. Figure <ref> illustrates three examples of this construction for k=3: one that is C_3-role coloured, one that is P_3^*-role coloured and one that is P_3^**-role coloured.















For all k≥ 2, the k-rcol problem is hard for graphs of vertex degree at most 3




Let G_ϕ be the graph constructed in the proof of Proposition <ref>. We modify G_ϕ to obtain a graph G'_ϕ such that G'_ϕ has a k-role colouring if and only if ϕ
has a not-all-equal satisfying assignment. To obtain G'_ϕ we add to
G_ϕ three cycles C={u_1,…,u_2k-1},C'={u'_1,…,u'_2k},C”={u”_1,…,u”_2k}.
We also add the edges u_1 v_n^2, u'_1 v_n^3 and u”_1 v_n^4.

Suppose that G'_ϕ has a k-role colouring r. By Lemma <ref> and Lemma <ref>
The role graph R of r is C_k or P_k^**. Observe that by Lemma <ref> {v_i^1: 1≤ i ≤ n}∪{ x_i^1 : 1 ≤ i ≤ n} is monochromatic. The rest of the argument follows as in Proposition <ref>: ϕ has a not-all-equal satisfying assignment.

Now suppose that ϕ has a not-all-equal satisfying assignment. We show that G'_ϕ has a P_k^**-role colouring
and therefore a k-role colouring. We know from Proposition <ref> that
G_ϕ has a P_k^**-role colouring. We will extend this colouring to G'_ϕ. We start by colouring C.
We set r(u_1)=1 (observing that r(v_n^2)=1), and r(u_2)=r(u_2k-1)=2. This forces us to set r(u_3)=r(u_2k-2)=3. If k=3 this completes
the colouring of C, otherwise we continue the colouring r(u_i)=r(u_2k-(i-1)=i. Observe that r(u_k)=k and r(u_2k-(k-1))=k, and u_k is adjacent to u_2k-(k-1)=u_k+1. This completes the colouring of C.
To colour C' we set r(u'_1)=1 (observing that r(v_n^3=2). Since C' is a cycle of length 2k,
we may colour its vertices 1,1,…,k,k,…,3,2. We colour C” similarly, but starting at r(u”_1)=2.
This completes the colouring and the proof.



We now show how to increase the length of every cycle, and every H_i graph, to 
prove that  is a limit class.



Let G be a graph and let (H,p) be in {(C_k,k),(P_k,2k-2),(P_k^*,2k-1),(P_k^**,2k)}. Let e be an edge in G, and let G' be obtained from G by performing p subdivisions of e. Then G is H-role-colourable if and only if G' is.



Clearly if G is H-role colourable, then G' is H-role colourable.
Let e=uv and let s_1,…,s_p be the vertices added as a result of subdividing e, so that us_1, s_1s_2,…,s_p v are all edges of G'. Let r' be an H-role colouring
of G'. By Lemma <ref>, r'(u)=r'(s_p) and r'(v)=r'(s_1). Therefore
we can H-role colour G by setting r(u)=r'(u),r(v)=r'(v).






 is a limit class for k-rcol.





We show that k-rcol is -hard for the class S_j of (K_1,4,C_3,…,C_j, H_1,…,H_j)-free graphs for all j≥3. Fix some arbitrary constant j.
We further modify G'_ϕ to obtain a graph G_ϕ^j ∈ S_j such that G_ϕ^j has a k-role colouring
if and only if ϕ has a not-all-equal satisfying assignment. Observe that G'_ϕ is (K_1,4,C_3,H_1,H_2,H_3)-free.
Let p(k)=2k(k-1)(2k-1), and note that p(k) is a constant. For each edge e of G'_ϕ, we perform jp(k) subdivisions
of e to obtain G_ϕ^j. Certainly, G_ϕ^j is (K_1,4,C_3,…,C_j,H_1,…,H_j)-free.
The following are equivalent:


    
  * G'_ϕ has a k-role colouring
    
  * G'_ϕ has a P_k^**-role colouring
    
  * G^j_ϕ has a P_k^**-role colouring
    
  * G^j_ϕ has a k-role colouring


We have shown that 1.⇒2.; that 3.⇒4. is immediate. By Lemma <ref>, 2.⇒3. and 4.⇒1., as required. Since G_ϕ^j has a k-role colouring if and only if G'_ϕ has a k-role colouring
if and only if ϕ has a not-all equal satisfying assignment, the proof is complete.






 §.§ Minimality of the Limit Class


To prove that the limit class described above is minimal, we introduce the following minimality criterion as a lemma.


(<cit.>)
Let M be the set of minimal forbidden induced subgraphs for a limit class X for some family . Then X is minimal if and only if for each G∈ X there exists a finite subset T ⊂ M such that Free(T∪{G}) is in .


Our application of this lemma is identical to that of <cit.>; we repeat it here for completeness.
We require the following auxiliary results. 


(<cit.>) Let Y be a monotone class of graphs. If there is at least one graph in ∖ Y then the treewidth of Y is bounded.





The k-role colouring problem can be solved in polynomial time if the input is restricted to a class of bounded treewidth.


This is an corollary of the fact that H-role colouring can be solved in polynomial time if
H has bounded maximum degree and the input graph G has bounded treewidth <cit.>.


We are now ready to prove Theorem <ref>. Let G be a graph in . Observe
that G is an induced subgraph of mS_jjj for some m and j; let M_j
be the set {K_1,4,C_3,…,C_2j+1,H_1,… H_2j+1}. The class of
({G}∪ M_j)-free graphs is a proper
subclass of ({mS_jjj}∪ M_j)-free graphs. By Lemma <ref>, it is enough to prove the following
result.



For all m,j≥1, the k-rcol problem is in  for ({mS_jjj}∪ M_j)-free graphs.



It is enough to show that Free({mS_jjj}∪ M_j) is a proper subclass of Free_m(mS_jjj).
Let G be a graph in Free({mS_jjj}∪ M_j), and suppose H is a subgraph of G isomorphic
to mS_jjj. By definition of G, V(H) does not induce a copy of mS_jjj. So there
must be at least one additional edge between two vertices of H. If there is an edge between
two vertices of the same connected component of H (i.e. of the same S_jjj), then 
there is necessarily a chordless cycle of length at most 2k+1 in G, which is a contradiction.
Similarly, a small chordless cycle appears if two of the components of H are connected by
at least two edges in G. Finally, if two components of H are connected by a single
edge in G, an induced subgraph isomorphic to H_i with i≤ 2k+1 appears, which is a contradiction.
This completes the proof of Theorem <ref>.




We conclude this section by observing that applying Lemma <ref>
directly to the construction in Proposition <ref> shows that 𝒮 is a boundary class for H-role-colouring in the case where H is a P_k^** (for k≥2) or a C_k (for k≥3). We note that these graphs are sparse. Previous results on k-role-colouring (e.g. <cit.>) have also made use of sparse role graphs. In the next section we show that when the role graph is very dense, we can also find a boundary property.










§ COUPON COLOURINGS



Observe that 2-ccol is P_2^**-rcol, and so 
is a boundary class in this case. We consider k-coupon colourings
for k≥ 3.
Let ℱ_k be the class of forests of maximum vertex degree at most k. In this section we prove the following theorem.


*th:couponboundaryTheorem <ref>


ℱ_k is a boundary class for the k-ccol problem for all k≥3.




It is known that k-coupon colouring is -hard even when the input graph is k-regular <cit.>. This is not a hereditary property of graphs; taking the hereditary closure of the k-regular graphs yields the graphs of maximum degree k. Let G be a graph of maximum degree k. Our goal is to produce a graph G' which is (K_1,k+1,C_3,…,C_j)-free, such that G has a k-role colouring if and only if G' has.
The general idea is illustrated in Figure <ref>. We will replace every edge uv with a pair of trees of depth much larger than j, such that u is adjacent to v' and v adjacent to u'. We add edges between the leaves of these trees to force the colour of u to match the colour of u' (and v to match v') while avoiding cycles of length less than j.
We call this operation gemel implantation. The construction for k=j=3 is illustrated in Figure <ref>.
Let G be the 3-regular graph on the left of the figure, and G' be the graph on the right, obtained by a gemel implantation. 
Observe that any 3-coupon colouring ϕ of G' has ϕ(u)=ϕ(u') (and by symmetry, ϕ(v)=ϕ(v')).
Thus, G' has a 3-coupon colouring if and only if G' has.
Furthermore, there is no triangle in the gemel, nor can there be a triangle of G' including both u and v. 
Now let G” be the graph obtained by performing a gemel implantation at every edge of G. 
By the previous discussion, G” has a 3-coupon colouring if and only if G has.
Furthermore, G” is 3-regular and triangle-free, i.e. (K_1,4,C_3)-free.
Clearly G” can be obtained from G in polynomial time. 
Thus, 3-coupon colouring is -hard for (K_1,4,C_3)-free graphs.






In order to generalise this argument to prove Theorem <ref>, we need to show that we can perform a gemel implantation in k-regular graphs that avoids arbitrarily large cycles (and preserves k-coupon colourability).
We note that, for the argument to go through, the gemel implantation must be performed in polynomial time. Our construction is of constant size, and therefore gemel implantation at every edge takes O(n^2) time as required. Unfortunately, the constants involved are large; in order to achieve girth j, N vertices must be added to each edge where log ^* N > j. 
We suspect there is a more efficient construction, but note that it will
have size at least exponential in j.


We demonstrate our construction by first presenting a family of
regular graphs of high girth. These graphs
consist of two cycles and a matching between them. 
We then show how to use the matching to create the gemel implantation.


 §.§ High girth graph G_(n,k)


We define a family of graphs with girth Ω (log ^* |V|). For ease of notation, let a_n=a_(n,r). Let a_0=1, and let a_n+1=a_n+(k-1)^a_n. We create a graph G_(n,k) as follows. Let V(G_(n,k))={0,1}×{ 0,1,…, k-2} ^a_n. We read strings from right to left. 
Let V_0 be all the vertices whose strings end with 0, and V_1 be all the vertices whose strings end with 1. Add an edge between two vertices in V_0 if the number expressed (in base (k-1)) by their strings differ by 1 (k-1)^a_n, and do the same for V_1. This creates two cycles of length (k-1)^a_n. We add a matching between these cycles to obtain a 3-regular graph. For a vertex v in V_0, for 0≤ i ≤ n-1, let x_i be the number expressed by the first a_i digits of v. Let w be the vertex in V_1 that differ from v only in the digits at positions a_0+(x_0+1),… a_n-1+(x_n-1+1), namely by adding 1 to these digits k-1. Add edges vw for all v ∈ V_0. Let e:V_0→ V_1 be the bijective function with e(v)=w as described. Change the last 0 to a 1. Now, G_(n,k) is a 3-regular graph.
For example, the graph G_(2,3), shown in Figure <ref> has vertex set { 0,1} ^4 and girth 4.  



G_(n,k) has girth Ω (log ^* a_n).





If a cycle in G_(n,k) is entirely in V_0 or V_1, then it has length (k-1)^a_n. Let C be a cycle in G_(n,k) that contains an edge vw ∈ [V_0,V_1], where [A,B] is the set of edges ab with one endpoint a ∈ A and one endpoint b ∈ B. Then v and w differ in the digit at position a_n-1+x_n-1 (among others). Suppose a cycle starts at v,w,…. To complete a cycle, the digit at a_n-1+x_n-1 must be returned to its state in v (among other digits). This can be done in two ways: along an edge within V_0 or V_1, or along an edge in [V_0,V_1]. Remember that moving along an edge within V_0 or V_1 changes the represented number of the string by 1, while moving along an edge in [V_0,V_1] changes a set of n digits across the string.
 
Let two vertices be close if they are distance ≤ (k-1)^a_n-2 apart within G[V_0] or in G[V_1], and far otherwise.

We define a good edge in G_(n,k) as an edge ∈ [V_0,V_1] which has one of its endpoints close to another vertex that differs in the digit at position a_n-1+x_n-1.
Other edges in ∈ [V_0,V_1] are bad. 
Good edges have an endpoint that has only (k-1)s or only 0s at positions a_n-2+1,…,a_n-1. Without loss of generality, suppose that vw is a good edge, with v ∈ V_0,w∈ V_1, such that v has only 0s at positions a_n-2+1,…,a_n-1. Then w has exactly one 1 in the substring at positions a_k-2+1,…,a_k-1 (namely, at position a_k-2+x_k-2, and 0s otherwise. 

Then, w is far away in G[V_1] from any other endpoint of a good edge. Therefore, there is no cycle of length ≤ (k-1)^a_n-2 that uses only good edges from [V_0,V_1].

Let C=(v,w,u,…) be a cycle in G_(n,k) that uses at least one bad edge vw ∈ [V_0,V_1]. Then, v and w differ at position a_n-1+x_n-1. The path w,u… along C must reach a vertex x∈ V_0 that is equal to v in the first a_n-1 bits, or a vertex y ∈ V_1 that is equal to w in the first a_n-1 bits, such that the edge xe(x) or ye^-1(y) changes the digit at position a_n-1+x_n-1 back to its state at v. Then either the path v,w,…,x or the path w,…,y correspond to a cycle in G_(n-1,k). To complete C, by symmetry, there must then also be a path x,e(x),…,v or a path y,e^-1(y),…,v, which again correspond to a cycle in G_(n-1,k). Therefore, 

    g(G_(n,k))≥min{ 2g(G_(n-1,k)),(k-1)^a_n-2},     g(G_(1,k)≥3.
 Then, 
    g(G_(n,k))=Ω(2^n)=Ω(2^log^* a_n)=Ω(log^* |V|).















 §.§ Gemel implantation using G_(n,k)

Given a k-regular graph G, we choose a value n, and create a k-regular graph G' by replacing every edge vw with two edges uv' and u'v, and two planar (k-1)-ary trees of depth a_n, rooted at v' and u'. We number the leaves using k-ary strings of length a_n, by their position in the tree (in the natural way), and add either a 0 or 1 at the end for the tree rooted at v' or u', respectively. We call these leaf sets V_0 and V_1. We add the matching in [V_0,V_1] based on the girth graph G_(n,k). Note that we do not add the cycles within V_0,V_1. Finally, we contract all leaf-edges of both trees, and end up with a k-regular graph G'. (Once we have done this for all edges of G.) Figure <ref> shows an example sketch based on G_(2,3).




*prop:ccolProposition <ref>

The k-ccol problem is -complete for graphs of girth at least g for all g≥ 3.





To prove Proposition <ref>, we use a construction for the k-coupon colouring problem that is a slight variation on the matchings in the graph G_(n,k) that forces the pairs (v,v') and (u,u') to be mono-coloured in a k-coupon colouring, while still having girth that grows with n. This results in a graph G' of high girth that has a k-coupon colouring if and only if G has a k-coupon colouring. 

Let a_0=1, and let a_n+1=a_n+2*(k-1)^a_n. Note the factor of 2. Given a k-regular graph G, we choose a value n and, for each edge of G, add the two (k-1)-ary trees of depth a_n, T_0 rooted at v' and T_1 rooted at u'. Label the vertices of the trees by (k-1)-ary strings in the natural way, adding a 0 or a 1 at the end for T_0 and T_1, respectively. The bijective function e that adds the matching now takes two steps. The first step is very similar to G_(n,k), except that we change only digits at even positions. For every digit at positions a_0+2*(x_0+1)-1,… a_n-1+2*(x_n-1+1)-1, increase it by 1 and take k-1. Change the last 0 of the string to a 1. Then, remove the second-to last digit (adjacent to the final 1) and insert it in the first position. The first digit becomes the second digit, etc…For example, if n=1 and k=4, then the string 𝐜𝐲𝐚𝐧0𝐨𝐫𝐚𝐧𝐠𝐞11𝐨𝐫𝐚𝐧𝐠𝐞110002 has a_0=1 and x_0=2. The trit at position a_0+2*(x_0+1)-1=6 changes to 0+1 3=1. The last 0 changes to a 1. Finally, the first trit is removed and inserted into second to last position. The resulting string is 𝐜𝐲𝐚𝐧11𝐨𝐫𝐚𝐧𝐠𝐞210002𝐨𝐫𝐚𝐧𝐠𝐞1.
Without loss of generality, suppose that v' has colour 0 in a k-coupon colouring. The colours of u, as well as the children of v', are undetermined, but we know that the grand children of v' in T_0 must have colors 1,…,k-1. Then, the colours of the great-grandchildren of v' are undetermined, but we know the sets of colours for each set of great-great-grandchildren of v' that share a common parent. In other words, up to isomorphism, we know the colours of vertices in the tree that are at even distance from v'. We describe a function f_0 that maps the even-distance vertices of this tree to colours in a k-coupon colouring, such that any valid k-coupon colouring matches this colouring up to ismorphism. Note that for any vertex w in the tree, d(v',w) is one less than the length of the string. Let 

    f_0(w)=∑_j=0^d(v',w)/2-1 (t_2j+1+1) k,

where t_j is the value of the digit at position j. For example, the colour of the vertex with string 011110002 is

    f_0(011110002)=(2+1)+(0+1)+(1+1)+(1+1) =0 4.

To check that this corresponds to a valid k-coupon colouring, we need to verify two things:


  (1) Vertices receive colours that are different from their grandparents,

  (2) vertices receive colours that are different from their siblings.

Note that the colour of a vertex can be computed from the colour of its grandparent by adding 1+t_1. Since 0 ≤ t_1 ≤ k-2, and t_1 distinguishes siblings, these two conditions are met.

The leaves of T_0 do receive a colour, but they will disappear in the final graph. This colour must be passed on to the vertices at the level above the leaves of T_1. For every leaf-parent of T_1, this means that all leaves of T_0 matched to its children must have the same colour. This is the colour it must adopt to satisfy the leaf-parents in T_0, once all leaves have been deleted. Therefore, we need a function f_1 that maps vertices of T_1 that are at even distance from u' to colours in a k-coupon colouring. Let this function be 


    f_1(w)=∑_j=0^d(u',w)-1/2 (t_2j+1+1) k.


For example, the color of the vertex with string 11210002 is

    f_1(11210002)=(2+1)+(0+1)+(1+1)+(1+1) =0 4.

To check that this corresponds to a valid k-coupon colouring, we need to verify three things:


  (1) Vertices receive colours that are different from their grandparents,

  (2) vertices receive colours that are different from their siblings,

  (3) leaf-parents in T_1 receive the same colour as the leaves of T_0 that are matched to their children.

Condition (1) and (2) are verified as before, and condition (3) is verified by the fact that the function of a leaf-parent in T_1 sums exactly the same set of numbers as a leaf of T_0 that maps to any of its children. 

Finally, we also note that the children of u' in T_1 have colors in the set {0,…,k-2}+1, implying that v' must have colour 0. By a similar argument, the vertices u and u' must also have the same colour (independent of the colour of v and v').


Finally, we note that g(G')=Ω (log (g(G_(n,k)))), because for two leaves (or leaf-parents) w_1,w_2 in one of the trees T_i we have 
    d_T_i(w_1,w_2)=Ω( log d_G_(n,k)[V_i](w_1,w_2)).
 The removal/insertion of the first digit changes this distance only by a constant factor. 









 §.§ Minimality



We apply the minimality criterion to show that the limit class _k is a boundary class for k-ccol. Let G be a graph in _k. Clearly G is an induced subgraph of some perfect k-regular tree. 
Let t be the smallest integer such that G is an induced subgraph of T_k^t. Since the M∪{G}-free graphs form a subset of the M∪{T_k^t}-free graphs for any set M, it is enough to show that the criterion holds for T_k^t for all  t.
We make use of Lemma <ref>.




Every (T_k^t,K_1,k+1,C_3,…,C_2t+2)-free graph has a vertex of degree less than k.



Let H be (T_k^t,K_1,k+1,C_3,…,C_2t+2)-free, and suppose every vertex of H has degree at least k. Since H is (K_1,k,C_3)-free, h is in fact k-regular. Let v be a vertex of H and consider its radius t neighbourhood N^t(v).
Since H is k-regular and contains no induced cycle of length shorter than 2t+2, it follows that N^t(v) induces a T_k^t. This contradiction completes the proof.



The k-coupon colouring problem can be solved in polynomial time for (T_k^t,K_1,k+1,C_3,…,C_2t+1)-free graphs.



By the previous lemma, graphs in this class have no k-coupon colouring.
Thus the problem is trivially solvable in polynomial time.









§ DISCUSSION


We end the paper with a discussion of the uniqueness of our boundary classes and give some open problems. A complete list of boundary classes for a given problem Π would characterise the finitely defined hereditary classes for which Π is easy (assuming ≠). A set of boundary classes {_1,_2,…} for Π contains every boundary class if and only if for all i and for all G∈_i, Π is solvable in polynomial time for G-free graphs. 



 §.§ Role colouring 2K_2-free graphs


We can immediately see that, for k ≥ 4, there must be a boundary class for k-rcol
different from , due to the following result.


(<cit.>) For k≥ 4, k-rcol is -hard for (2K_2,C_4,C_5)-free graphs.


We resolve the case k=2, leaving k=3 open. We need the 
following lemma.



Let G be a connected 2K_2-free graph. If G has a maximal independent set I of size at least 2, then the graph induced by V(G) ∖ I is connected.



Let u,v∈ I and consider S=V∖ I. If |S|=1 then by definition the graph induced by S is connected. Let x,y ∈ S and suppose x is a neighbour of u. If y is a neighbour of v, then x and y are adjacent, otherwise u,v,x,y induce a 2K_2. If y is not a neighbour of v, then there must be a vertex z ∈ S which is adjacent to v, otherwise G is not connected. Now z must be adjacent to x, otherwise u,v,x,z induce a 2K_2. Similarly, z must be adjacent to y. Therefore there is a path from x to y as required.






Every 2K_2-free graph with at least 2 vertices has a 2-role colouring.
Furthermore, such a colouring can be computed in polynomial time.




If G is disconnected or is a clique, then a 2-role colouring
is easy to find.
Otherwise, G is a connected graph with a pair
of non-adjacent vertices u,v. Let I be a maximal 
independent set containing u,v. By Lemma <ref>,
the graph induced by V(G) ∖ I is connected.
So we can colour all vertices of I with colour 1 and 
all vertices of V(G) ∖ I with colour 2. 
Since I can be found in polynomial time, this completes the proof.





 §.§ Coupon colouring claw-free graphs


Our boundary class for k-ccol is also not unique due to the following
result.


(<cit.>) The k-ccol problem is -complete for 
k-regular claw-free graphs.


The authors of <cit.> only state the theorem for k-regular graphs, but it is easy
to see that their construction (which follows Theorem 5 in <cit.>) is claw-free.








 §.§ Open problems


The fact that k-role colouring 2K_2-free graphs is easy for k=2 but hard for k≥ 4 suggests the following questions.


What is the computational complexity of 3-role colouring 2K_2-free graphs?



Which boundary classes for k-role colouring exist inside 2K_2-free graphs (for k ≥ 4)?


For k-role colouring, the important class of claw-free graphs is a minimal open case.
Also, claw-free graphs must contain a boundary class for k-coupon colouring. This suggests
claw-free graphs as a topic of further study.


What is the computational complexity of k-role colouring claw-free graphs?










Which boundary classes for k-coupon colouring exist inside claw-free graphs?


plain





