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 , 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 of a graph is 2-homogeneous if
where denotes the open neighbourhood of . When such a colouring exists, let 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 satisfies . The upper bound is attained by .
The sharpness example is already observed in [5 p. 358]. Each part of 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 be the biadjacency matrix of a cubic bipartite graph. Its two parts have the same size. The graph is det-extremal if , where denotes the permanent of . Equivalently, for fixed orders of the two parts, all perfect matchings contribute with the same sign to .
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 be a 3-connected det-extremal cubic bipartite graph. Then admits a fall 3-colouring. In particular, .
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 is total dominating if every vertex of has a neighbour in , including the vertices of itself. The total domatic number 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 be the bipartition. Since is not det-extremal, . Choose disjoint total dominating sets and add any remaining vertices to . Both sets remain total dominating and now partition . Define
Every edge joins to , whose palettes are disjoint, so the colouring is proper. Every vertex has a neighbour in each of . Hence each vertex of sees exactly the colours , and each vertex of sees exactly the colours .
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 and Corollary , 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 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 denote the class generated from by vertex-sums. By McCuaig’s theorem [9], the graphs in are precisely the 3-connected det-extremal cubic bipartite graphs [4 Theorem 2.2].
It therefore suffices to show that every graph in 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 . 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 of triples, where is the colour at the th port and is the prescribed colour at the other end of its half-edge. We require for every . The 3-pole realises if it has a proper colouring with these port colours in which every vertex sees both other colours, counting at the th port.
Let denote the number of distinct entries of a triple . Among the proper boundary states, define
A state in 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 will be realised by the 3-poles used in the construction. In particular, if , every proper choice of is allowed. The state permits the deleted vertex to be restored with colour 0.
We shall also use colours on individual edge ends. Let and . 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 , let be the triple of colours at its own ends and let be the corresponding triple at the opposite ends. An assignment for satisfies
Thus every vertex outside has a single colour, whereas a vertex of may be replaced by a 3-pole realising its assigned state. At this stage, the three ends at a vertex of 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 . 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 , and let be the set of isolated vertices of . Every assignment for can be changed into an assignment for with the same boundary, by recolouring only ends of edges of .
Proof. Put and take an assignment for with the prescribed boundary. For each , let be the common colour at its three incident ends.
Choose a maximal matching of . On each edge , interchange the colours at its ends. The edge remains proper, and each vertex covered by now has two colours at its own ends. Since has no isolated vertices and is maximal, every uncovered vertex has a covered neighbour . On , recolour only the end at with the third colour distinct from . The end at still has colour , since .
Now for every . All the new states at these vertices belong to . Only ends of edges inside were changed, so the states at vertices outside and the prescribed boundary are preserved.
Activations
Let be a fall 3-colouring of with prescribed boundary, again counting the exterior colours at its ports. Let be independent. On an internal edge with we may change the end at to the third colour distinct from and . We call this change an activation at . The end at retains colour , and boundary half-edges are kept fixed. For , the triple still uses two colours since the neighbours of lie outside . One or two activations at leave both the original colour and a new colour in . If all three ends are changed, the two colours in give two different new colours in . Thus any nonempty set of activations at gives a state in . It remains to determine which changes preserve at the vertices outside .
For , write its neighbour colours as . Call the neighbour of colour the minority neighbour of and the other two its majority neighbours. An exterior neighbour can have either role and is always outside . Activating an incidence with changes its neighbour colour from to or from to . 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 on . For each with , consider the following possibilities.
(a) If consists of the minority neighbour alone, its incidence with cannot be activated.
(b) If consists of the two majority neighbours, join them by an edge of . At most one of the two incidences with may be activated, and either choice is possible.
(c) In every other case all incidences from to may be activated together. Call each vertex of free.
Lemma 3.2. Every vertex of can be activated while preserving the boundary state and the neighbourhood condition outside if and only if every component of 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 be a tree component with no free vertex. Each activation available in uses an edge of as in (b), and each such edge can serve only one end. Since , at least one vertex cannot be activated. □
Point and line obstructions
By vertex transitivity of we may take to be the line 123. Label the six retained lines by
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 , write for its set of points and for its set of lines. No point of lies on a line of . The auxiliary multigraph is the disjoint union of and , so point and line activations can be chosen independently.
Fix a fall 3-colouring with prescribed boundary. The point majority graph has the seven points as vertices and joins the two equally coloured points on each retained line. For the line majority graph , 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 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 cannot all be activated precisely when one of the following holds.
(P1) is the vertex set of a tree component of containing an outside point.
(P2) and contains an isolated vertex of .
The vertices of cannot all be activated precisely when 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 be a component of on points containing no free vertex. If is an edge of and , then must be selected and the minority point on the line must be unselected. Otherwise is free by (c). Hence by (b), and . It follows that is a whole component of with the same edges.
Suppose is an outside point. Every other point lies on a retained line with . A point of the same colour is joined to in . A selected point of a different colour would make free by (c) on their common line. Hence is the colour class of . Conversely, if is the vertex set of such a component of , its selected points on any line form the majority pair or the minority singleton, whenever the line meets . Thus and has no free vertex. Lemma 3.2 gives (P1).
If 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 . As above, a component of 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 must be exactly one unmarked colour class. Conversely, for such a class every majority pair in the clique gives an edge of 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.
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 . Every permutation of these points is linear on the subspace and extends to 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 is bichromatic, we may take . Up to interchanging the first two ports, the first two entries of are 00, 02 or 22, and the last entry is 0 or 1. The rows , , , , , of Table 1 give these six possibilities. With , their exterior triples are 000, 221, 001, 020, 220, 021, respectively. If has three colours, then has exactly two by properness and the definition of . Its repeated colour must occur at the two ports whose own colours differ from it. Renaming the colours and ordering the ports gives .
| Point obstructions | Line obstructions | |||||
| 000 | 112 | 0000 | 222211 | |||
| 000 | 112 | 0112 | 202010 | , | , | |
| 001 | 110 | 0112 | 202012 | , | ||
| 001 | 112 | 0112 | 202010 | , | ||
| 001 | 122 | 0122 | 201010 | , | ||
| 001 | 220 | 0221 | 101021 | , | ||
| 012 | 100 | 0012 | 202112 | , | ||
| 001 | 120 | 0101 | 221022 |
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 records the colours of the points 4, 5, 6, 7, and records the colours of the lines , , , , , , 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
The entries follow from Lemma 3.3. For instance, in row the components of the point majority graph on and are trees, whereas the component on contains a cycle. The only unmarked line colour class of size at most two is . Thus row fails on the point side exactly for or , and on the line side exactly for .
We shall also use the following automorphisms, each of which fixes the three ports individually.
| outside points | retained lines | |
Table 2.
If is an initial colouring, then has the same boundary state, and its obstructions are the images under of those of . The same applies to and . We are now ready to prove the boundary extension lemma.
Lemma 3.4. For every and every boundary state of , there is an assignment for with boundary .
Proof. By Lemma 3.1, it suffices to consider an independent set . Write , where consists of points and of lines. By Lemmas 3.2 and 3.3, an initial colouring suffices whenever neither nor is one of its listed obstructions.
. Consider , and . If , then contains only ports, so it is a point obstruction for neither nor . Their line obstruction families are and , which are disjoint. The other possible obstruction for is . This set occurs in neither line column for and , and their point obstruction families and are disjoint.
or . For the first state use , , and for the second use , . In each pair there is no line obstruction, and the two point obstruction families are disjoint.
. The colourings and have disjoint point obstruction families and disjoint line obstruction families. For both colourings to fail, one of the following must hold.
Both alternatives contradict the independence of . Indeed, lie on , lies on , and lies on .
or . For , the colourings , have disjoint point obstruction families. Their only common line obstruction is , so both can fail only for this choice of . Similarly, , can both fail only for . At least one of the four colourings therefore suffices. For the same argument applies to the pairs , and , . Their respective common line obstructions are and .
. If , then is a point obstruction for neither nor . Their only line obstructions are and , respectively. Suppose now that . Apply the case to . The three ends at point then have colour . Recolour only the end at point of its boundary half-edge with colour . Its two internal ends retain colour , and its exterior neighbour retains colour . The boundary half-edge remains proper, while gives a state in . No internal end is changed, and the new outer boundary state is .
These cases cover every state in and complete the proof.
Extension through vertex-sums
We now apply Lemma 3.4 to the vertex-sum construction of . Its prescribed states allow simultaneous substitutions, including substitutions at adjacent vertices.
Lemma 3.5. Let and let . The 3-pole can be obtained from vertex-deleted Heawood graphs by successive substitutions at vertices. It realises every boundary state in .
Proof. We first establish the recursive representation by induction on the number of vertex-sums. The assertion is immediate for . Suppose that the final sum deletes and , and that survives on the -side. Then is obtained from by replacing with . The induction hypothesis gives both pieces with their attachments in the prescribed order. If is a port, its boundary half-edge is inherited by the corresponding port of .
We prove the assertion about boundary states by induction on this representation. The base case is Lemma 3.4 with . In the induction step, consider the outer copy of and let be the set of its vertices occupied by smaller 3-poles. Given a boundary state in , Lemma 3.4 assigns compatible endpoint colours with relation at the vertices of and relation 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 .
Restoring the deleted vertex gives the required three-colouring.
Lemma 3.6. Every graph in admits a fall 3-colouring.
Proof. Let and choose . Lemma 3.5 gives a colouring of with boundary state . Restore with colour 0. Each port then sees its prescribed exterior colour, and sees both 1 and 2. The resulting colouring is a fall 3-colouring of .
We can now prove Corollary 1.2.
Proof of Corollary 1.2. By McCuaig’s characterisation, , so Lemma 3.6 gives a fall 3-colouring. The lower bound yields the equality.
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 be a det-extremal cubic bipartite graph of connectivity two. It has a 2-edge cut with simple cubic bipartite closures , such that and is not det-extremal.
Proof. For either shore, let , be its bipartition classes and let count its outgoing edges incident with these classes. Degree counting gives , where . Consequently : 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 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 . Thus is simple and 3-connected, and McCuaig’s characterisation gives .
Let be the other closure, with markers in and in , so that the cut edges are , . Choose perfect matchings of containing and avoiding , respectively, and similarly for in . Such choices exist by three-edge-colourability of cubic bipartite multigraphs. Let be the cycles containing the markers in and . Switching an alternating cycle of length permutes the matched images cyclically and changes the matching sign by . Since is det-extremal, .
Replace the markers in by , . The resulting cycle has length and alternates with respect to
Det-extremality of therefore gives , whence .
If were parallel to an original edge , we could take . Then would have length two, contradicting the congruence just obtained. These are the only possible parallel edges in , so is simple. Finally, switching reverses a perfect-matching sign, proving that is not det-extremal.
We shall combine the colourings of the two closures using the following elementary lemma.
Lemma 3.8. Let be disjoint graphs with proper -homogeneous colourings using at most colours. Choose edges and . The graph obtained by deleting and adding also has a proper -homogeneous colouring using at most colours.
Proof. Use the same -colour palette on both graphs. Since the ends of each chosen edge have different colours, a permutation of the palette on makes and . 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 were established in § 1. If 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 . A cut vertex in a cubic graph would give a bridge, so has connectivity two or three. If is det-extremal and 3-connected, apply Lemma 3.6. Otherwise choose the closures , of Lemma 3.7. Lemma 3.6 colours with three colours, and Lemma 2.1 colours with at most four colours. Regard both as colourings from the same four-colour palette. Let , be their markers, labelled so that the original cut edges are , . Lemma 3.8 combines the two colourings.
Concluding remarks
The four-colour bound remains sharp at connectivity exactly two. Let be obtained from two disjoint copies of by deleting edges , and adding , . The resulting graph is cubic and bipartite, hence 2-connected, and is a vertex cut.
Suppose that admits a fall 3-colouring. Within each copy of , the two non-terminal vertices in each part must have the same colour. The neighbourhood condition then forces the terminals , 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 .
The graph 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 . Indeed, let be such a graph. By Brooks’ theorem [1], 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 . This observation also occurs in the proof of Li and Zhou’s Theorem 3.1 [7]. On the other hand, 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]R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194–197.
- [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]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]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]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]D. Labbate and P. Romaniello, Strong edge-colourings of truncations of cubic graphs, arXiv:2601.4950v1 (2026).arxiv.org/abs/2610.41950
- [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]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]W. McCuaig, Even dicycles, J. Graph Theory 35 (2000), 46–68.