Graph Coloring

What is this?

Seat a wedding party where certain pairs refuse to sit together. Draw an edge for every conflict, and the question "can this be arranged in two rooms?" becomes "is this graph two-colourable?" — answered by walking it and alternating colours, checking that no edge ever joins two people in the same room.

This chapter takes it one step further: not can it be split, but into the most groups possible, with the rule that every edge must cross between adjacent groups.

💡 Fun fact: a graph can be split into layers this way exactly when it is bipartite — that is, when it contains no odd-length cycle. The check falls out of the BFS for free: if any edge connects two nodes on the same layer, an odd cycle exists and no valid grouping is possible. The same test decides two-colourability, whether a relation can be modelled as two disjoint sets, and whether a scheduling conflict graph can be split across two shifts.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: BFS from a node assigns every other node a layer, and a valid grouping exists precisely when no edge stays within a layer. To maximise the number of groups, try every starting node in a component, keep the deepest layering, and sum across components — they are independent.

1. The layered BFS

def deepest_layering(start, adj):
    depth = {start: 1}
    queue = deque([start])
    best = 1
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if v not in depth:
                depth[v] = depth[u] + 1
                best = max(best, depth[v])
                queue.append(v)
            elif abs(depth[v] - depth[u]) != 1:
                return -1            # an edge inside a layer → odd cycle
    return best

The validity test is abs(depth[v] - depth[u]) != 1. Every edge must connect adjacent layers; an edge joining two nodes at the same depth (or two apart) means the graph cannot be layered at all.

2. Why every start must be tried

The depth you achieve depends on where you begin. Starting at the middle of a path graph gives a shallow layering; starting at an end gives the deepest one. Since the problem wants the maximum number of groups, you must run the BFS from every node in the component and keep the best result.

That makes the algorithm O(V × (V + E)) — acceptable because the constraints are small, and worth stating explicitly so the interviewer knows you chose it rather than missed something.

3. Components are independent

Groups in one connected component have nothing to do with groups in another, so the totals simply add. Run the search per component and sum the best depths. If any component fails the bipartite test, the whole answer is -1 — one impossible piece makes the arrangement impossible.

4. A 30-second worked example

A path 1 — 2 — 3 — 4:

start at 1:   layers  1:1  2:2  3:3  4:4   → depth 4  ✅ best
start at 2:   layers  2:1  1:2  3:2  4:3   → depth 3
start at 3:   layers  3:1  2:2  4:2  1:3   → depth 3
start at 4:   layers  4:1  3:2  2:3  1:4   → depth 4

                                  component best = 4

Now add the edge 1 — 3, creating the odd cycle 1—2—3—1:

start at 1:   1:1, 2:2, 3:2   → the edge 1—3 connects layers 1 and 2 ✓
              but the edge 2—3 connects layer 2 to layer 2  ✗
                                              → return -1

Three nodes in a triangle can never be layered, which is the same reason a triangle cannot be two-coloured.

5. Where you'll actually meet this

• Scheduling and shift allocation. Splitting staff across two shifts when certain pairs cannot work together.
• Register allocation. Compilers colour an interference graph so that no two simultaneously-live variables share a register.
• Frequency assignment. Radio towers within range of each other need different frequencies — colouring with more than two colours.
• Conflict and exam timetabling. Students taking two courses create an edge; the chromatic number is the number of exam slots needed.
• Data modelling. Verifying that a relation really is bipartite — users and items, authors and papers — before treating it as such.

6. Problems in this chapter

▶ Divide Nodes Into the Maximum Number of Groups

Split every node into numbered groups so that each edge joins adjacent group numbers, maximising the count. BFS-layer from every node in each component, keep the deepest valid layering, and sum across components.
Pattern: bipartite check + deepest layering per component. Target: O(V × (V + E)) time, O(V) space.

7. Common pitfalls 🚫

• Testing only one start node. The deepest layering depends on where you begin; missing this returns a valid but suboptimal answer.
• Forgetting disconnected components. The graph is not guaranteed connected, and each component contributes independently.
• Returning the maximum instead of the sum across components.
• Checking only depth[v] == depth[u]. The requirement is that the depths differ by exactly one, so a gap of two is also invalid.
• Propagating -1 incorrectly. One failing component makes the whole answer -1, not just that component's contribution.
• Using DFS for the layering. Depths from a DFS do not correspond to BFS layers, and the adjacency test stops being valid.
• Assuming small graphs mean anything goes. Say the complexity out loud — O(V × (V + E)) is a deliberate choice licensed by the constraints.

8. Key takeaways

1. A conflict is an edge, and "can these be separated?" is a colouring question.
2. Layered BFS validates and measures at once — the same walk checks bipartiteness and gives the depth.
3. Edges must join adjacent layers. Anything else means an odd cycle.
4. Try every start when maximising depth; the answer depends on where you begin.
5. Components are independent, so their bests add — but one failure poisons the whole result.
6. Bipartite means no odd cycle. That equivalence is the theory behind the code.
7. Why interviewers like it: the BFS is routine, so the signal is whether you spot that starting position matters and that components must be handled separately.

Order: Divide Nodes Into the Maximum Number of Groups.