betaFeedback

WorksMathematics

On 2-Homogeneous Colourings of Cubic Bipartite Graphs

Abstract

A proper vertex colouring is 2-homogeneous if every open neighbourhood contains exactly two colours. We show that every cubic bipartite graph admits a 2-homogeneous colouring with at most four colours, proving a conjecture of Janicová, Madaras, Soták and Lužar. For 3-connected det-extremal cubic bipartite graphs, we establish the stronger bound χh(2)(G)=3χ_h^{(2)}(G) = 3, showing that every such graph admits a fall 3-colouring.

Introduction

All graphs considered are finite, simple and connected unless stated otherwise. Connectivity means vertex connectivity. A proper vertex colouring cc of a graph GG is 2-homogeneous if

∣c(NG(v))∣=2for every v∈V(G),|c(N_G(v))| = 2 \qquad\text{for every } v \in V(G),

where NG(v)N_G(v) denotes the open neighbourhood of vv. When such a colouring exists, let χh(2)(G)\chi_h^{(2)}(G) be the minimum number of colours it uses. Every such colouring uses at least three colours. For a cubic graph, the colours on the three neighbours of each vertex have multiplicities two and one.

Janicová, Madaras, Soták and Lužar proved that every cubic bipartite graph admits a 2-homogeneous colouring with at most six colours and conjectured that four colours suffice [5 Theorem 1.2 and Conjecture 4.1]. They also proved the four-colour bound for regular bipartite graphs of degree at least four. Our main result settles their conjecture and answers Problem 5.1 of Lužar and Soták [8] for cubic bipartite graphs.

Theorem 1.1. Every cubic bipartite graph GG satisfies 3≤χh(2)(G)≤43 \le\chi_h^{(2)}(G) \le4. The upper bound is attained by K3,3K_{3,3}.

The sharpness example is already observed in [5 p. 358]. Each part of K3,3K_{3,3} is the neighbourhood of every vertex in the other part and must therefore use exactly two colours. Properness forces these two pairs of colours to be disjoint. Conversely, assigning two colours to each part gives a 2-homogeneous four-colouring.

Let BB be the biadjacency matrix of a cubic bipartite graph. Its two parts have the same size. The graph is det-extremal if ∣det⁡B∣=per⁡B|\det B| = \operatorname{per} B, where per⁡B\operatorname{per} B denotes the permanent of BB. Equivalently, for fixed orders of the two parts, all perfect matchings contribute with the same sign to det⁡B\det B.

A proper 2-homogeneous colouring with three colours is precisely a fall 3-colouring: every closed neighbourhood contains all three colours [3]. Equivalently, its three colour classes are independent dominating sets. Our proof gives the following three-colour result.

Corollary 1.2. Let GG be a 3-connected det-extremal cubic bipartite graph. Then GG admits a fall 3-colouring. In particular, χh(2)(G)=3\chi_h^{(2)}(G) = 3.

The non-det-extremal case of Theorem 1.1 is a consequence of Choi, Kwon and Park’s characterisation in terms of the total domatic number [2 Theorem 1.4]. Their theorem provides a partition into two total dominating sets. Intersecting these sets with the bipartition gives the four colour classes. For det-extremal graphs of connectivity three, we use McCuaig’s construction from the Heawood graph and prove an extension lemma with prescribed boundary colours. The case of connectivity two follows from a cut lemma of Labbate and Romaniello [6], based on the structure theorem of Funk et al. [4].

Section 2 gives the non-det-extremal construction. Section 3 treats the det-extremal case and completes the proofs of Theorem 1.1 and Corollary 1.2; the boundary extension lemma is proved in § 3.2. Section 4 gives a sharp example of connectivity two and relates the result to the question for general cubic graphs.

Non-det-extremal graphs

A set D⊆V(G)D \subseteq V(G) is total dominating if every vertex of GG has a neighbour in DD, including the vertices of DD itself. The total domatic number dt(G)d_t(G) is the maximum number of pairwise disjoint total dominating sets. Choi, Kwon and Park [2 Theorem 1.4] prove that a connected cubic graph is det-extremal if and only if its total domatic number is one. For bipartite graphs, their definition using the adjacency matrix is equivalent to the definition using the biadjacency matrix above. We use the following consequence.

Lemma 2.1. Every non-det-extremal cubic bipartite graph admits a proper 2-homogeneous colouring with at most four colours.

Proof. Let V(G)=X∪YV(G) = X \cup Y be the bipartition. Since GG is not det-extremal, dt(G)≥2d_t(G) \ge2. Choose disjoint total dominating sets D0,D1D_0, D_1 and add any remaining vertices to D1D_1. Both sets remain total dominating and now partition V(G)V(G). Define

c(v)={1,v∈X∩D0,2,v∈X∩D1,3,v∈Y∩D0,4,v∈Y∩D1.c(v)= \begin{cases} 1, & v \in X \cap D_0,\\ 2, & v \in X \cap D_1,\\ 3, & v \in Y \cap D_0,\\ 4, & v \in Y \cap D_1. \end{cases}

Every edge joins XX to YY, whose palettes are disjoint, so the colouring is proper. Every vertex has a neighbour in each of D0,D1D_0,D_1. Hence each vertex of XX sees exactly the colours 3,43,4, and each vertex of YY sees exactly the colours 1,21,2. □\square

Equivalently, one may apply the incidence criterion of [2 Theorem 3.5] to the neighbourhood hypergraph on each part. A direct construction using perfect matchings and an even directed cycle is given in [6 Lemmas 3.3–3.4].

Det-extremal graphs

To prove Theorem 1.11.1 and Corollary 1.21.2, we first construct three-colourings for the 3-connected det-extremal graphs. We then use a 2-edge cut to obtain the four-colour bound in connectivity two.

Vertex-sums and boundary states

Let HH be the Heawood graph, the incidence graph of the Fano plane. Each of its seven lines contains three points, any two points determine a unique line, and any two lines meet in a unique point. A vertex-sum deletes one vertex from each of two disjoint cubic graphs and joins their two sets of former neighbours by a matching. Let H\mathcal{H} denote the class generated from HH by vertex-sums. By McCuaig’s theorem [9], the graphs in H\mathcal{H} are precisely the 3-connected det-extremal cubic bipartite graphs [4 Theorem 2.2].

It therefore suffices to show that every graph in H\mathcal{H} admits a fall 3-colouring. We shall prove a boundary extension lemma that allows these colourings to be combined across vertex-sums.

For the Heawood construction, we use the colour set {0,1,2}\{0,1,2\}. Deleting a vertex from a cubic graph and retaining its three incident half-edges gives a 3-pole. Its three boundary vertices are called ports. Fix an ordering of the half-edges. A boundary state is a pair (E,P)(E,P) of triples, where pip_i is the colour at the iith port and eie_i is the prescribed colour at the other end of its half-edge. We require ei≠pie_i \ne p_i for every ii. The 3-pole realises (E,P)(E,P) if it has a proper colouring with these port colours in which every vertex sees both other colours, counting eie_i at the iith port.

Let q(W)q(W) denote the number of distinct entries of a triple WW. Among the proper boundary states, define

(E,P)∈T  ⟺  q(P)=1,q(E)=2,(E,P) \in\mathcal{T} \iff q(P)=1,\quad q(E)=2,
(E,P)∈R  ⟺  q(P)≥2,(q(P),q(E))≠(3,3).(E,P) \in\mathcal{R} \iff q(P)\ge2,\quad(q(P),q(E))\ne(3,3).

A state in T\mathcal{T} describes a single coloured vertex: its own colour is repeated at its three incident ends, and the opposite ends use the other two colours. The states in R\mathcal{R} will be realised by the 3-poles used in the construction. In particular, if q(P)=2q(P) = 2, every proper choice of EE is allowed. The state (000,112)(000,112) permits the deleted vertex to be restored with colour 0.

We shall also use colours on individual edge ends. Let F=H−zF = H - z and S⊆V(F)S \subseteq V(F). Assign a colour to each end of each internal edge and prescribe the two colours at every boundary half-edge. Opposite ends must have distinct colours. At u∈V(F)u \in V(F), let PuP_u be the triple of colours at its own ends and let EuE_u be the corresponding triple at the opposite ends. An assignment for SS satisfies

(Eu,Pu)∈{R,u∈S,T,u∉S.(E_u,P_u) \in\begin{cases} \mathcal{R}, & u \in S,\\ \mathcal{T}, & u \notin S. \end{cases}

Thus every vertex outside SS has a single colour, whereas a vertex of SS may be replaced by a 3-pole realising its assigned state. At this stage, the three ends at a vertex of SS need not have the same colour.

The boundary extension lemma

We first show how an assignment for an independent set extends to an arbitrary selection of vertices. We then study recolourings of individual edge ends in a fall 3-colouring of FF. An auxiliary multigraph determines when all selected vertices can be recoloured. Finally, explicit initial colourings cover the seven types of boundary state.

Reduction to an independent set

Lemma 3.1. Let S⊆V(F)S \subseteq V(F), and let II be the set of isolated vertices of F[S]F[S]. Every assignment for II can be changed into an assignment for SS with the same boundary, by recolouring only ends of edges of F[S∖I]F[S \setminus I].

Proof. Put U=S∖IU = S \setminus I and take an assignment for II with the prescribed boundary. For each u∈Uu \in U, let cuc_u be the common colour at its three incident ends.

Choose a maximal matching MM of F[U]F[U]. On each edge uv∈Muv \in M, interchange the colours at its ends. The edge remains proper, and each vertex covered by MM now has two colours at its own ends. Since F[U]F[U] has no isolated vertices and MM is maximal, every uncovered vertex uu has a covered neighbour ww. On uwuw, recolour only the end at uu with the third colour distinct from cu,cwc_u,c_w. The end at ww still has colour cwc_w, since uw∉Muw \notin M.

Now q(Pu)=2q(P_u) = 2 for every u∈Uu \in U. All the new states at these vertices belong to R\mathcal{R}. Only ends of edges inside F[U]F[U] were changed, so the states at vertices outside UU and the prescribed boundary are preserved. □\square

Activations

Let cc be a fall 3-colouring of FF with prescribed boundary, again counting the exterior colours at its ports. Let SS be independent. On an internal edge uvuv with u∈Su \in S we may change the end at uu to the third colour distinct from c(u)c(u) and c(v)c(v). We call this change an activation at uu. The end at vv retains colour c(v)c(v), and boundary half-edges are kept fixed. For u∈Su \in S, the triple EuE_u still uses two colours since the neighbours of uu lie outside SS. One or two activations at uu leave both the original colour and a new colour in PuP_u. If all three ends are changed, the two colours in EuE_u give two different new colours in PuP_u. Thus any nonempty set of activations at uu gives a state in R\mathcal{R}. It remains to determine which changes preserve TT at the vertices outside SS.

For v∉Sv \notin S, write its neighbour colours as a,a,ba,a,b. Call the neighbour of colour bb the minority neighbour of vv and the other two its majority neighbours. An exterior neighbour can have either role and is always outside SS. Activating an incidence with vv changes its neighbour colour from aa to bb or from bb to aa. The triple becomes monochromatic in just two cases, when only the minority position is changed or when both majority positions and no other position are changed.

Define a multigraph DD on SS. For each v∉Sv \notin S with N(v)∩S≠∅N(v) \cap S \ne\varnothing, consider the following possibilities.

(a) If N(v)∩SN(v) \cap S consists of the minority neighbour alone, its incidence with vv cannot be activated.

(b) If N(v)∩SN(v) \cap S consists of the two majority neighbours, join them by an edge of DD. At most one of the two incidences with vv may be activated, and either choice is possible.

(c) In every other case all incidences from SS to vv may be activated together. Call each vertex of N(v)∩SN(v) \cap S free.

Lemma 3.2. Every vertex of SS can be activated while preserving the boundary state and the neighbourhood condition outside SS if and only if every component of DD contains a free vertex or a cycle. Two parallel edges count as a cycle.

Proof. Perform all the activations in (c). In a component containing a free vertex, root a spanning tree at that vertex and direct its edges away from the root. For each directed edge use (b) to activate its head. In a component containing a cycle, extend the cycle to a connected spanning subgraph with just that cycle. Direct the cycle cyclically and all other edges away from it. Again every vertex requiring an activation receives one.

Conversely, let CC be a tree component with no free vertex. Each activation available in CC uses an edge of CC as in (b), and each such edge can serve only one end. Since ∣E(C)∣=∣V(C)∣−1|E(C)| = |V(C)| - 1, at least one vertex cannot be activated. □

Point and line obstructions

By vertex transitivity of HH we may take zz to be the line 123. Label the six retained lines by

a=145,b=167,c=246,d=257,e=347,f=356.a = 145,\qquad b = 167,\qquad c = 246,\qquad d = 257,\qquad e = 347,\qquad f = 356.

The points 1, 2, 3 are the ports. The points 4, 5, 6, 7, which lie outside the deleted line, are called the outside points. For an independent set SS, write XX for its set of points and YY for its set of lines. No point of XX lies on a line of YY. The auxiliary multigraph DD is the disjoint union of D[X]D[X] and D[Y]D[Y], so point and line activations can be chosen independently.

Fix a fall 3-colouring with prescribed boundary. The point majority graph MPM_P has the seven points as vertices and joins the two equally coloured points on each retained line. For the line majority graph MLM_L, take the six retained lines and three fixed vertices representing the exterior neighbours of the ports. At each point, join its two equally coloured neighbours. A retained line is marked if it is joined in MLM_L to a fixed vertex. Whenever a marked line is selected, it is free by (c).

Lemma 3.3. For the fixed colouring, the vertices of XX cannot all be activated precisely when one of the following holds.

(P1) XX is the vertex set of a tree component of MPM_P containing an outside point.

(P2) X⊆{1,2,3}X \subseteq\{1,2,3\} and XX contains an isolated vertex of MPM_P.

The vertices of YY cannot all be activated precisely when YY is an entire colour class of the retained lines of size one or two and none of its lines is marked.

Proof. First consider the point vertices. Let CC be a component of DD on points containing no free vertex. If xyxy is an edge of MPM_P and x∈V(C)x \in V(C), then yy must be selected and the minority point on the line xyxy must be unselected. Otherwise xx is free by (c). Hence xy∈E(D)xy \in E(D) by (b), and y∈V(C)y \in V(C). It follows that CC is a whole component of MPM_P with the same edges.

Suppose x∈V(C)x \in V(C) is an outside point. Every other point lies on a retained line with xx. A point of the same colour is joined to xx in MPM_P. A selected point of a different colour would make xx free by (c) on their common line. Hence X=V(C)X = V(C) is the colour class of xx. Conversely, if XX is the vertex set of such a component of MPM_P, its selected points on any line form the majority pair or the minority singleton, whenever the line meets XX. Thus D[X]=CD[X] = C and has no free vertex. Lemma 3.2 gives (P1).

If CC contains only ports, it consists of a single isolated port because two ports lie together only on the deleted line. Selecting an outside point would make the port free on their common line. Conversely, if only ports are selected, an isolated port has no available activation. It is the minority point on each of its two retained lines, and no other port lies on either. This proves (P2).

For the line vertices, any two retained lines meet in a point. Lines of the same colour form the majority pair at that point, so every line colour class induces a clique in MLM_L. As above, a component of DD on lines with no free vertex contains the whole clique of its colour. No line in it can be marked. A selected line of another colour would give a free activation where it meets a line of the clique. Thus YY must be exactly one unmarked colour class. Conversely, for such a class every majority pair in the clique gives an edge of DD and there are no free vertices. The clique is a tree exactly when it has one or two vertices. The conclusion follows from Lemma 3.2. □\square

Initial colourings of the Heawood 3-pole

We may permute the three colours and the three ports. Indeed, the points of the deleted line are the three nonzero vectors of a two-dimensional subspace of F23\mathbb{F}_2^3. Every permutation of these points is linear on the subspace and extends to F23\mathbb{F}_2^3 by fixing a vector outside it. The resulting automorphism preserves incidence and hence also preserves independence of the selected vertices.

There are seven types of boundary state up to these permutations. If PP is bichromatic, we may take P=112P = 112. Up to interchanging the first two ports, the first two entries of EE are 00, 02 or 22, and the last entry is 0 or 1. The rows A0A_0, BB, CC, DD, E0E_0, F0F_0 of Table 1 give these six possibilities. With P=112P = 112, their exterior triples are 000, 221, 001, 020, 220, 021, respectively. If PP has three colours, then EE has exactly two by properness and the definition of R\mathcal{R}. Its repeated colour must occur at the two ports whose own colours differ from it. Renaming the colours and ordering the ports gives (E,P)=(001,120)(E, P) = (001, 120).

EEPPQQLLPoint obstructionsLine obstructions
A0A_00001120000222211P∗\mathcal{P}_*{e,f}\{e,f\}
A1A_10001120112202010{4}\{4\}, {3,7}\{3,7\}{a,c}\{a,c\}, {e}\{e\}
BB0011100112202012{7}\{7\}, {3,4}\{3,4\}∅\varnothing
CC0011120112202010{4}\{4\}, {3,7}\{3,7\}{a,c}\{a,c\}
DD0011220122201010{4}\{4\}, {1,5}\{1,5\}{a}\{a\}
E0E_00012200221101021{7}\{7\}, {3,4}\{3,4\}{e}\{e\}
F0F_00121000012202112{7}\{7\}, {1,6}\{1,6\}∅\varnothing
JJ0011200101221022P2\mathcal{P}_2{c}\{c\}

Table 1. Initial colourings of the Heawood 3-pole. The last two columns list the exact selected sets for which point or line activation fails. An empty family means that every selection on that side can be activated.

Table 1 gives the initial colourings for these cases. The string QQ records the colours of the points 4, 5, 6, 7, and LL records the colours of the lines aa, bb, cc, dd, ee, ff, in this order. In each row the points of a retained line have two colours and the line has the third colour. Every point sees both colours different from its own when the exterior neighbours of the ports are included.

For each colouring, the last two columns list the selections of points and lines for which activation fails. We use

P∗={X:∅≠X⊆{1,2,3}},P2={X:2∈X⊆{1,2,3}}.\mathcal{P}_* = \{X : \varnothing\ne X \subseteq\{1,2,3\}\}, \qquad\mathcal{P}_2 = \{X : 2 \in X \subseteq\{1,2,3\}\}.

The entries follow from Lemma 3.3. For instance, in row CC the components of the point majority graph on {4}\{4\} and {3,7}\{3,7\} are trees, whereas the component on {1,2,5,6}\{1,2,5,6\} contains a cycle. The only unmarked line colour class of size at most two is {a,c}\{a,c\}. Thus row CC fails on the point side exactly for X={4}X = \{4\} or X={3,7}X = \{3,7\}, and on the line side exactly for Y={a,c}Y = \{a,c\}.

We shall also use the following automorphisms, each of which fixes the three ports individually.

outside pointsretained lines
α\alpha(4 5)(6 7)(4\ 5)(6\ 7)(c d)(e f)(c\ d)(e\ f)
β\beta(4 6)(5 7)(4\ 6)(5\ 7)(a b)(e f)(a\ b)(e\ f)
γ=αβ\gamma= \alpha\beta(4 7)(5 6)(4\ 7)(5\ 6)(a b)(c d)(a\ b)(c\ d)

Table 2.

If cc is an initial colouring, then αc\alpha c has the same boundary state, and its obstructions are the images under α\alpha of those of cc. The same applies to β\beta and γ\gamma. We are now ready to prove the boundary extension lemma.

Lemma 3.4. For every S⊆V(F)S \subseteq V(F) and every boundary state (E,P)∈R(E, P) \in\mathcal{R} of FF, there is an assignment for SS with boundary (E,P)(E, P).

Proof. By Lemma 3.1, it suffices to consider an independent set SS. Write S=X∪YS = X \cup Y, where XX consists of points and YY of lines. By Lemmas 3.2 and 3.3, an initial colouring suffices whenever neither XX nor YY is one of its listed obstructions.

(E,P)=(000,112)(E, P) = (000, 112). Consider A0A_0, A1A_1 and αA1\alpha A_1. If X∈P∗X \in\mathcal{P}_*, then XX contains only ports, so it is a point obstruction for neither A1A_1 nor αA1\alpha A_1. Their line obstruction families are {{a,c},{e}}\{\{a, c\}, \{e\}\} and {{a,d},{f}}\{\{a, d\}, \{f\}\}, which are disjoint. The other possible obstruction for A0A_0 is Y={e,f}Y = \{e, f\}. This set occurs in neither line column for A1A_1 and αA1\alpha A_1, and their point obstruction families {{4},{3,7}}\{\{4\}, \{3, 7\}\} and {{5},{3,6}}\{\{5\}, \{3, 6\}\} are disjoint.

(E,P)=(001,110)(E, P) = (001, 110) or (012,100)(012, 100). For the first state use BB, αB\alpha B, and for the second use F0F_0, αF0\alpha F_0. In each pair there is no line obstruction, and the two point obstruction families are disjoint.

(E,P)=(001,112)(E, P) = (001, 112). The colourings CC and αC\alpha C have disjoint point obstruction families and disjoint line obstruction families. For both colourings to fail, one of the following must hold.

X∈{{4},{3,7}},Y={a,d},X∈{{5},{3,6}},Y={a,c}.\begin{aligned} X &\in\{\{4\}, \{3, 7\}\}, \quad Y = \{a, d\},\\ X &\in\{\{5\}, \{3, 6\}\}, \quad Y = \{a, c\}. \end{aligned}

Both alternatives contradict the independence of SS. Indeed, 4,54, 5 lie on aa, 77 lies on dd, and 66 lies on cc.

(E,P)=(001,122)(E, P) = (001, 122) or (001,220)(001, 220). For (001,122)(001, 122), the colourings DD, αD\alpha D have disjoint point obstruction families. Their only common line obstruction is Y={a}Y = \{a\}, so both can fail only for this choice of YY. Similarly, βD\beta D, γD\gamma D can both fail only for Y={b}Y = \{b\}. At least one of the four colourings therefore suffices. For (001,220)(001, 220) the same argument applies to the pairs E0E_0, γE0\gamma E_0 and αE0\alpha E_0, βE0\beta E_0. Their respective common line obstructions are {e}\{e\} and {f}\{f\}.

(E,P)=(001,120)(E, P) = (001, 120). If 2∉S2 \notin S, then XX is a point obstruction for neither JJ nor αJ\alpha J. Their only line obstructions are {c}\{c\} and {d}\{d\}, respectively. Suppose now that 2∈S2 \in S. Apply the case (001,110)(001, 110) to S∖{2}S \setminus\{2\}. The three ends at point 22 then have colour 11. Recolour only the end at point 22 of its boundary half-edge with colour 22. Its two internal ends retain colour 11, and its exterior neighbour retains colour 00. The boundary half-edge remains proper, while q(P2)=2q(P_2) = 2 gives a state in R\mathcal{R}. No internal end is changed, and the new outer boundary state is (001,120)(001, 120).

These cases cover every state in R\mathcal{R} and complete the proof. □\square

Extension through vertex-sums

We now apply Lemma 3.4 to the vertex-sum construction of H\mathcal{H}. Its prescribed states allow simultaneous substitutions, including substitutions at adjacent vertices.

Lemma 3.5. Let G∈HG \in\mathcal{H} and let r∈V(G)r \in V(G). The 3-pole G−rG-r can be obtained from vertex-deleted Heawood graphs by successive substitutions at vertices. It realises every boundary state in R\mathcal{R}.

Proof. We first establish the recursive representation by induction on the number of vertex-sums. The assertion is immediate for G=HG = H. Suppose that the final sum deletes a∈V(A)a \in V(A) and b∈V(B)b \in V(B), and that rr survives on the AA-side. Then G−rG-r is obtained from A−rA-r by replacing aa with B−bB-b. The induction hypothesis gives both pieces with their attachments in the prescribed order. If aa is a port, its boundary half-edge is inherited by the corresponding port of B−bB-b.

We prove the assertion about boundary states by induction on this representation. The base case H−zH-z is Lemma 3.4 with S=∅S = \varnothing. In the induction step, consider the outer copy of H−zH-z and let SS be the set of its vertices occupied by smaller 3-poles. Given a boundary state in R\mathcal{R}, Lemma 3.4 assigns compatible endpoint colours with relation R\mathcal{R} at the vertices of SS and relation T\mathcal{T} at the other vertices. By induction, each smaller 3-pole admits the colouring specified at its three ports. On every edge joining two pieces, the colour at either end is the prescribed exterior colour for the other end. The colourings therefore combine to give the required state on G−rG-r. □\square

Restoring the deleted vertex gives the required three-colouring.

Lemma 3.6. Every graph in H\mathcal{H} admits a fall 3-colouring.

Proof. Let G∈HG \in\mathcal{H} and choose r∈V(G)r \in V(G). Lemma 3.5 gives a colouring of G−rG-r with boundary state (E,P)=(000,112)(E, P) = (000, 112). Restore rr with colour 0. Each port then sees its prescribed exterior colour, and rr sees both 1 and 2. The resulting colouring is a fall 3-colouring of GG. □\square

We can now prove Corollary 1.2.

Proof of Corollary 1.2. By McCuaig’s characterisation, G∈HG \in\mathcal{H}, so Lemma 3.6 gives a fall 3-colouring. The lower bound χH(2)(G)≥3\chi_{\mathcal{H}}^{(2)}(G) \ge3 yields the equality. □\square

Two-edge cuts and the four-colour bound

For a 2-edge cut, the closure of a shore is obtained by joining its two boundary vertices with a new edge, called its marker. We use the following lemma of Labbate and Romaniello [6 Lemma 3.18]. We include its proof, taking the decomposition cactus of Funk et al. [4] as a structural input.

Lemma 3.7. Let GG be a det-extremal cubic bipartite graph of connectivity two. It has a 2-edge cut with simple cubic bipartite closures PP, RR such that P∈HP \in\mathcal{H} and RR is not det-extremal.

Proof. For either shore, let X′X', Y′Y' be its bipartition classes and let dX,dYd_X,d_Y count its outgoing edges incident with these classes. Degree counting gives 3(∣X′∣−∣Y′∣)=dX−dY3(|X'|-|Y'|)=d_X-d_Y, where dX+dY=2d_X+d_Y=2. Consequently dX=dY=1d_X=d_Y=1: the boundary vertices lie in opposite parts and the closure is cubic and bipartite. At this stage a marker may be parallel to an original edge.

In the decomposition cactus, vertices represent classes joined by three edge-disjoint paths. Closing a class with its markers gives either a simple 3-connected cubic bipartite graph or a 3-bond, that is, two vertices joined by three parallel edges. Choose a non-cut vertex on an end cycle of the cactus. It has degree two, and its closure PP has one marker. By [4 Theorem 4.10], this piece is det-extremal. It cannot be a 3-bond, since its two original edges would already be parallel in GG. Thus PP is simple and 3-connected, and McCuaig’s characterisation gives P∈HP \in\mathcal{H}.

Let RR be the other closure, with markers e=uve=uv in PP and f=xyf=xy in RR, so that the cut edges are uyuy, vxvx. Choose perfect matchings p1,p0p_1,p_0 of PP containing and avoiding ee, respectively, and similarly r1,r0r_1,r_0 for ff in RR. Such choices exist by three-edge-colourability of cubic bipartite multigraphs. Let CP,CRC_P,C_R be the cycles containing the markers in p1△p0p_1 \triangle p_0 and r1△r0r_1 \triangle r_0. Switching an alternating cycle of length 2ℓ2\ell permutes the matched images cyclically and changes the matching sign by (−1)ℓ−1(-1)^{\ell-1}. Since PP is det-extremal, ∣CP∣≡2(mod4)|C_P| \equiv2 \pmod{4}.

Replace the markers in CP∪CRC_P \cup C_R by uyuy, vxvx. The resulting cycle has length ∣CP∣+∣CR∣|C_P|+|C_R| and alternates with respect to

M=((p1∪r1)∖{e,f})∪{uy,vx}.M=((p_1 \cup r_1)\setminus\{e,f\})\cup\{uy,vx\}.

Det-extremality of GG therefore gives ∣CP∣+∣CR∣≡2(mod4)|C_P|+|C_R| \equiv2 \pmod{4}, whence ∣CR∣≡0(mod4)|C_R| \equiv0 \pmod{4}.

If ff were parallel to an original edge gg, we could take r0=(r1∖{f})∪{g}r_0=(r_1\setminus\{f\})\cup\{g\}. Then CRC_R would have length two, contradicting the congruence just obtained. These are the only possible parallel edges in RR, so RR is simple. Finally, switching CRC_R reverses a perfect-matching sign, proving that RR is not det-extremal.

We shall combine the colourings of the two closures using the following elementary lemma.

Lemma 3.8. Let G1,G2G_1,G_2 be disjoint graphs with proper 22-homogeneous colourings using at most kk colours. Choose edges uv∈E(G1)uv \in E(G_1) and xy∈E(G2)xy \in E(G_2). The graph obtained by deleting uv,xyuv,xy and adding uy,vxuy,vx also has a proper 22-homogeneous colouring using at most kk colours.

Proof. Use the same kk-colour palette on both graphs. Since the ends of each chosen edge have different colours, a permutation of the palette on G1G_1 makes c(u)=c(x)c(u)=c(x) and c(v)=c(y)c(v)=c(y). The two new edges are proper. At each of their four ends, the colour of the deleted neighbour equals that of the new neighbour. Every multiset of neighbour colours is therefore unchanged.

We are now ready to prove Theorem 1.1.

Proof of Theorem 1.1. The lower bound and equality for K3,3K_{3,3} were established in § 1. If GG is not det-extremal, apply Lemma 2.1. A cubic bipartite graph has no bridge: counting degrees on one shore of a bridge would give 3(∣X′∣−∣Y′∣)=±13(|X'|-|Y'|)=\pm1. A cut vertex in a cubic graph would give a bridge, so GG has connectivity two or three. If GG is det-extremal and 3-connected, apply Lemma 3.6. Otherwise choose the closures PP, RR of Lemma 3.7. Lemma 3.6 colours PP with three colours, and Lemma 2.1 colours RR with at most four colours. Regard both as colourings from the same four-colour palette. Let uvuv, xyxy be their markers, labelled so that the original cut edges are uyuy, vxvx. Lemma 3.8 combines the two colourings.

Concluding remarks

The four-colour bound remains sharp at connectivity exactly two. Let G∗G^{*} be obtained from two disjoint copies of K3,3K_{3,3} by deleting edges x1y1x_{1}y_{1}, x2y2x_{2}y_{2} and adding x1y2x_{1}y_{2}, y1x2y_{1}x_{2}. The resulting graph is cubic and bipartite, hence 2-connected, and {x1,y1}\{x_{1},y_{1}\} is a vertex cut.

Suppose that G∗G^{*} admits a fall 3-colouring. Within each copy of K3,3−xyK_{3,3}-xy, the two non-terminal vertices in each part must have the same colour. The neighbourhood condition then forces the terminals xx, yy to have the third colour and their external neighbours to have different colours. This contradicts the equality of the terminal colours in the other copy. Therefore, Theorem 1.1 gives χh(2)(G∗)=4\chi_{h}^{(2)}(G^{*})=4.

The graph G∗G^{*} is non-det-extremal: a perfect matching containing the two joining edges can be switched along a 4-cycle, reversing its sign. Thus, this example leaves open whether every det-extremal cubic bipartite graph of connectivity two admits a fall 3-colouring.

For cubic claw-free graphs, three colours suffice apart from K4K_{4}. Indeed, let G≠K4G \ne K_{4} be such a graph. By Brooks’ theorem [1], GG admits a proper 3-colouring. Each vertex has two adjacent neighbours, which use the two colours different from its own. The colouring is therefore 2-homogeneous, and χh(2)(G)=3\chi_{h}^{(2)}(G)=3. This observation also occurs in the proof of Li and Zhou’s Theorem 3.1 [7]. On the other hand, K4K_{4} admits no proper 2-homogeneous colouring, since the neighbours of each vertex have three distinct colours in every proper colouring.

The general question of Lužar and Soták is the following.

Question 4.1 ([8 Problem 5.1]). If a cubic graph admits a proper 2-homogeneous colouring, must it admit one with at most four colours?

Theorem 1.1 answers this question for bipartite graphs. The claw-free case has the stronger bound of three, whereas the question remains open for general cubic graphs.

References

  1. [1]R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194–197.
  2. [2]M. Choi, H. Kwon and B. Park, Det-extremal cubic graphs and the total domatic number, arXiv:2609.33902v1 (2026).arxiv.org/abs/2609.33902
  3. [3]J. E. Dunbar, S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, J. Knisely, R. C. Laskar and D. F. Rall, Fall colourings of graphs, J. Combin. Math. Combin. Comput. 33 (2000), 257–273.
  4. [4]M. Funk, B. Jackson, D. Labatte and J. Sheehan, Det-extremal cubic bipartite graphs, J. Graph Theory 44 (2003), 50–64. The theorem numbers used here are those of the authors’ manuscript.DOI
  5. [5]M. Janicová, T. Madaras, R. Soták and B. Lužar, From NMNR-coloring of hypergraphs to homogeneous coloring of graphs, Ars Math. Contemp. 12 (2017), 351–360.DOI
  6. [6]D. Labbate and P. Romaniello, Strong edge-colourings of truncations of cubic graphs, arXiv:2601.4950v1 (2026).arxiv.org/abs/2610.41950
  7. [7]X. Li and W. Zhou, The 2nd-order conditional 3-coloring of claw-free graphs, Theoret. Comput. Sci. 396 (2008), 151–157.DOI
  8. [8]B. Lužar and R. Soták, Homogeneous coloring of cubic graphs, in A. Onderko (ed.), Open problems of the 33rd Workshop on Cycles and Colourings, Nový Smokovec, Slovakia, 31 August–5 September 2025, Section 5, p. 6, Problems 5.1 and 5.2. arXiv:2511.02892v1 (4 November 2025).
  9. [9]W. McCuaig, Even dicycles, J. Graph Theory 35 (2000), 46–68.

Paper details

vlnc:W_ut7m33qv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents