Graph Coloring and Bipartite Check

DSA · Graphs

Theory

Graph coloring assigns a color to each vertex so that no two connected vertices share a color. The minimum number of colors needed is called the chromatic number. Checking whether a graph can be colored with just two colors is the same as asking whether it is bipartite: whether its vertices can be split into two groups with every edge going between the groups. This two-color check is easy: run BFS or DFS, give the start node color 0, give every neighbour the opposite color, and fail if you ever find an edge connecting two nodes of the same color. A graph is bipartite exactly when it has no odd-length cycle. Coloring with three or more colors is NP-hard in general, so greedy heuristics are used in practice.

Why we use it

Coloring models scheduling and assignment problems where conflicts must be kept apart: exam timetables, register allocation in compilers, frequency assignment for mobile towers, and matching problems.

When to use it

Use the bipartite check for "split into two teams with no conflict" problems. Use greedy coloring when you need a good, not necessarily optimal, schedule with many colors.

How it works

  1. Color start node 0
  2. BFS: for each neighbour
  3. Neighbour uncolored? Yes: Give it the opposite color. No: Compare colors.
  4. Same color as current node? Yes: Not bipartite. No: Continue.
  5. All edges checked: bipartite

Syntax

Bipartite check (BFS)   O(V + E)
Greedy coloring         O(V + E)
Optimal k-coloring      NP-hard

Example

from collections import deque

def is_bipartite(graph):
    color = {}
    for start in graph:
        if start in color:
            continue
        color[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if v not in color:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False, color
    return True, color

square = {"A": ["B", "D"], "B": ["A", "C"], "C": ["B", "D"], "D": ["A", "C"]}
triangle = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]}
print("Square:", is_bipartite(square))
print("Triangle:", is_bipartite(triangle)[0])

def greedy_color(graph):
    colors = {}
    for u in graph:
        used = {colors[v] for v in graph[u] if v in colors}
        colors[u] = next(c for c in range(len(graph)) if c not in used)
    return colors

print("Greedy colors:", greedy_color(triangle))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic