¶ Graph Theory Basics
¶ Competitive programming
¶ Graph Coloring — An Intuitive and Deep Introduction for Competitive Programmers
There are certain ideas in competitive programming that feel almost magical the first time you encounter them. You start with a problem that seems unrelated to graphs, something about schedules or resource sharing or avoiding conflicts, and when you peel back the layers you realize it’s secretly asking you to color a graph. It’s like discovering that a wide range of puzzles all belong to the same family, and once you learn the family’s tricks, you see solutions everywhere. Graph coloring is one of those ideas—simple to define, but vast in application, surprisingly tricky in theory, and incredibly useful in competitions.
At its core, the idea is disarmingly straightforward: assign colors to the vertices of a graph so that no two adjacent vertices share the same color. That’s it. From this small definition springs a whole universe of problems—some playful, some difficult, some deep enough to touch the highest levels of theoretical computer science. But in competitive programming, graph coloring represents something even more valuable: a way to reason cleanly about constraints, conflicts, and structure.
A 100-article course might seem excessive if you only know the textbook definition of coloring. But the truth is that graph coloring is less a single topic and more a doorway into a whole collection of techniques. You’ll find coloring at the heart of greedy algorithms, backtracking puzzles, tree problems, bipartite checks, scheduling tasks, interval assignments, register allocation, frequency assignments, and even certain dynamic programming formulations. It somehow manages to appear both in elementary problems suitable for beginners and in notoriously difficult tasks in high-level contests where the challenge lies not in the algorithm but in discovering that a coloring interpretation exists at all.
What makes graph coloring so fascinating is that it forces you to think about conflicts. When two things interact in a way that prevents them from sharing a resource or being assigned the same label, a coloring problem is hiding underneath. Imagine trying to schedule exams so that no student has two tests at the same time; that’s a graph coloring problem. Imagine assigning frequencies to radio towers so that neighboring towers don’t interfere; another coloring problem. Even in purely mathematical puzzles—like trying to design patterns or arrangements that avoid repetition—you often end up reasoning in terms of colors.
For competitive programmers, this perspective is incredibly empowering. Once you start seeing problems through the lens of graph coloring, complicated scenarios suddenly become cleaner. You realize that many messy constraint-based problems are just graphs waiting to be colored. The skill lies in identifying the correct graph structure, the right notion of adjacency, and the conditions that dictate how many colors you need. Sometimes the problem is easy and a simple greedy approach works. Sometimes it’s trickier and you need to combine coloring with BFS, DFS, or disjoint set structures. And sometimes the challenge lies in proving whether a coloring is even possible.
One of the reasons graph coloring is so central to this domain is because it sits at the intersection of algorithmic intuition and combinatorial reasoning. The basic greedy approach is easy to understand and implement, and often surprisingly effective for contest-style inputs. On the other hand, the deep theory behind coloring problems—chromatic numbers, critical graphs, planar graph theorems—offers a level of sophistication that teaches you to reason carefully about structure and limitations. This blend makes coloring both accessible and intellectually rich, appealing to programmers at every level.
Another reason coloring is worth studying deeply is its versatility. Many problems that appear unrelated to graphs at first glance can be transformed into graph-coloring formulations with the right perspective. For example, when you have intervals on a timeline and need to determine the minimum number of resources required without overlapping, you're essentially coloring an interval graph. When you want to check if a graph is bipartite—a foundational task in competitive programming—you are performing a 2-coloring. When you’re grouping elements under constraints that forbid certain pairs from being together, you're building and coloring a conflict graph. Even puzzles where you must avoid using the same option for adjacent elements have coloring hidden beneath them.
This versatility means that graph coloring is not something you learn once and never touch again. It becomes a recurring theme, popping up regularly in contests of all levels. The more comfortable you are with coloring, the faster you recognize where it fits. And in contests, recognition is often half the battle. Many problems are straightforward once you identify the right model. The difficulty is in seeing that the system the problem describes is really a graph, and that the constraints embedded in the text of the problem correspond directly to coloring rules.
What makes coloring especially useful in competitive programming compared to heavy theoretical computer science is that we rarely need the most general or the most optimal solution. Most contest problems ask for a special case—coloring a bipartite graph, coloring a tree, coloring an interval graph, or coloring something where a greedy strategy works elegantly. Only occasionally will you run into a general NP-hard graph-coloring problem disguised in a contest, and even then, the input size or structure typically provides a hint toward some clever trick, heuristic, or restricted property that makes the solution efficient.
But even the simplest coloring tasks teach valuable habits. Coloring trains you to think about interactions, to visualize adjacency, to model problems cleanly, and to reason about conflicts systematically. It develops your ability to see graphs where others see clutter. And it develops a kind of conceptual flexibility—an ability to reinterpret problems in forms that algorithms can attack efficiently.
This course aims to help you build that flexible intuition, step by step, through a wide range of explorations. Across the articles, you’ll encounter classical ideas like 2-coloring via BFS, greedy coloring with orderings, coloring based on degree heuristics, and specialized coloring for interval, chordal, and bipartite graphs. But you’ll also see higher-level insights: how coloring interacts with matchings, how tree decompositions help, how planar graphs behave differently, and how to detect hidden coloring constraints in problems that don’t look like graphs at all.
Growing comfortable with coloring also means becoming comfortable with proofs and arguments about structure. You’ll find yourself thinking about why certain graphs require a minimum number of colors, why others collapse easily into two, and how structural properties like cycles, cliques, or chordal characteristics affect coloring. These are not just theoretical pursuits—they often provide the backbone for contest solutions. Understanding that a tree is always 2-colorable, or that interval graphs can be colored optimally with a greedy sweep, or that planar graphs are always 4-colorable, helps unlock patterns that solve real problems.
One of the enjoyable parts of learning coloring deeply is that it encourages creativity. Sometimes you will be given a strict set of constraints that force a particular coloring strategy. Other times, the problem will allow you flexibility: you might color the graph in one way to satisfy certain constraints, then recolor parts of it to optimize something else, or use coloring as a framework for partitioning the graph into easier subproblems. You’ll encounter problems where the coloring is the final answer and others where the coloring is merely a tool to reach a different goal.
A beautiful aspect of graph coloring, rarely appreciated at first, is that it naturally connects to optimization. For example, minimizing the number of colors corresponds to optimizing some resource allocation. Maximizing a distance between colors on a graph corresponds to spacing out conflicting tasks. Assigning weights to vertices can lead to weighted coloring problems. And many scheduling tasks translate almost perfectly into coloring interpretations. This conceptual bridge between pure combinatorics and practical optimization is one of the reasons graph coloring stands out as a topic that remains relevant even outside purely competitive environments.
As you dive deeper, you’ll also discover several specialized coloring themes that rarely appear in beginner resources but frequently surface in more advanced problems: edge coloring, list coloring, dynamic coloring, modular coloring, and frequency assignment models. Some of these seem theoretical at first, but each has at least one competitive-programming scenario where it becomes essential. Learning these variations early makes you far more confident when facing unfamiliar problems.
A key skill you’ll develop through this course is the ability to identify the minimal framing of a problem. Many tasks are much simpler when viewed through the right abstraction. A complicated set of rules about which elements can coexist might turn into a simple edge between vertices. A messy list of constraints might become a small graph where degrees and cliques reveal everything you need. Once you strip the problem down to its graph-theoretic core, the path forward often becomes clearer.
Another practical advantage of mastering graph coloring is how well it pairs with implementation strategies you already know—depth-first search, breadth-first search, sorting, greedy priority queues, dynamic programming, and even bitmasking. You begin to see how coloring can be layered onto these techniques, or how these techniques help you identify structures relevant to coloring. This interplay of concepts makes coloring a powerful tool not only theoretically but also practically.
One of the subtle joys of studying coloring is the shift in your thought process over time. In the beginning, coloring feels like a strict, almost mechanical task: “assign colors so neighbors don’t share.” But as you grow, you start making observations without consciously thinking. You begin to notice that a graph with no odd cycles must be bipartite. You start suspecting that intervals sorted by start time are probably an interval graph whose coloring is trivial. You catch yourself building conflict graphs automatically whenever you read constraints about things that cannot occur together. This instinct—this reflex to transform problems—is one of the most valuable skills in competitive programming.
There’s also something comforting about coloring. Even in difficult problems, the idea that we’re assigning labels in a way that avoids conflict gives a sense of structure. As chaotic as some competitive-programming problems can look at first glance, coloring is one of those techniques that cuts through the chaos. It gives clarity, boundaries, and order. For many programmers, this clarity is what turns graph problems from intimidating to enjoyable.
As you journey through these articles, you’ll experience not just the algorithms but also the mindset behind coloring. You’ll see how expert programmers read problems slowly and deliberately until they find the hidden graph. You’ll learn how they classify the type of graph subconsciously, how they decide whether a simple greedy method suffices, and how they recognize when deeper structure, like bipartiteness or interval behavior, is at play. You’ll also see how they deal with rare challenges—cases where coloring is impossible or where they must justify the minimum number of colors needed.
By the time you finish this course, graph coloring will no longer feel like a topic you occasionally encounter. It will feel like a natural extension of your problem-solving toolkit. You’ll find yourself applying it instinctively, using it to simplify problems, and recognizing coloring patterns even in tasks that never mention graphs explicitly. You’ll be comfortable writing reliable implementations, confident in your ability to reason through constraints, and familiar with both classical results and contest-oriented tricks.
Most importantly, coloring will become something you enjoy—not just as an algorithmic technique, but as a way of thinking about problems. It blends logic with creativity, structure with intuition, and simplicity with depth. It teaches you not only how to color graphs but how to uncover the hidden structure in the problems you face.
This introduction opens the door to a long, rich exploration. Ahead lies a full journey into the techniques, insights, variations, applications, and tricks that make graph coloring one of the most fascinating topics in competitive programming. And as you move through the series, you’ll gradually build a level of mastery that will serve you far beyond contests.
Let’s begin the journey into graph coloring—a topic that looks simple from the outside but reveals new beauty each time you look closer.
¶ Graph Theory Basics
¶ Beginner Level:
1. Introduction to Graph Theory in Competitive Programming
2. What is a Graph? Basic Definitions and Concepts
3. Types of Graphs: Directed and Undirected
4. Vertices, Edges, and Their Importance
5. Graph Representation: Adjacency Matrix and Adjacency List
6. Understanding Degree of a Vertex
7. Walks, Paths, and Cycles in Graphs
8. Simple Graphs, Multi-Graphs, and Pseudographs
9. Connected and Disconnected Graphs
10. Subgraphs and Induced Subgraphs
11. Graph Isomorphism: Basic Concept and Properties
12. Understanding Bipartite Graphs
13. Weighted and Unweighted Graphs
14. Graph Traversals: BFS vs. DFS
15. Depth-First Search (DFS) Algorithm
16. Breadth-First Search (BFS) Algorithm
17. Applications of BFS and DFS in Graph Theory
18. Topological Sorting of Directed Acyclic Graphs (DAG)
19. Understanding the Shortest Path Problem
20. Graph Connectivity: Basic Definitions and Algorithms
¶ Intermediate Level:
21. Strongly Connected Components (SCC) in Directed Graphs
22. Finding Strongly Connected Components Using Kosaraju's Algorithm
23. Finding SCC Using Tarjan’s Algorithm
24. Graph Coloring: Basics and Applications
25. DFS and BFS for Finding Connected Components
26. Eulerian Paths and Circuits
27. Hamiltonian Paths and Cycles
28. Planar Graphs and Their Properties
29. Graph Representations: Incidence Matrix and Edge List
30. Connected vs. Disconnected Components in Graphs
31. Spanning Trees: Definition and Properties
32. Prim’s Algorithm for Minimum Spanning Tree
33. Kruskal’s Algorithm for Minimum Spanning Tree
34. Dijkstra's Algorithm for Shortest Path
35. Bellman-Ford Algorithm for Shortest Path
36. Floyd-Warshall Algorithm for All-Pairs Shortest Path
37. Breadth-First Search for Finding Shortest Path in Unweighted Graphs
38. Bidirectional BFS for Faster Path Finding
39. Handling Negative Weight Edges in Graphs
40. Graph Representation in Competitive Programming: Trade-offs
¶ Advanced Level:
41. Dynamic Programming on Graphs: Basics and Techniques
42. Graph Traversals on Large Graphs: Optimizations
43. Floyd-Warshall Algorithm and Path Reconstruction
44. Shortest Path Algorithms with Constraints
45. A Search Algorithm for Pathfinding*
46. Handling Graph Cycles: Negative Cycles in Bellman-Ford
47. Johnson’s Algorithm for All-Pairs Shortest Path
48. Graph Matching Algorithms: Basic Concepts
49. Maximum Bipartite Matching Using DFS
50. Hungarian Algorithm for Maximum Matching
51. Kuhn-Munkres Algorithm for Optimal Assignment
52. Maximum Flow Problem in Graphs
53. Ford-Fulkerson Algorithm for Maximum Flow
54. Edmonds-Karp Algorithm for Maximum Flow
55. Dinic’s Algorithm for Maximum Flow
56. Min-Cost Max-Flow Problem
57. Graph Cut and Max Flow Min Cut Theorem
58. Network Flow Applications in Competitive Programming
59. Strongly Connected Components in Directed Graphs
60. Tarjan’s Algorithm for Finding Bridges in Graphs
61. Finding Articulation Points in Graphs
62. Biconnected Components in Graphs
63. Cycle Detection in Directed Graphs
64. Eulerian Circuit and Path Algorithms in Directed Graphs
65. Graph Embedding and Graph Representations
66. Advanced Techniques for Graph Traversals
67. Graph Decomposition and Dynamic Connectivity
68. Graph Partitioning Algorithms
69. Greedy Algorithms for Graph Problems
70. Approximation Algorithms for Graph Problems
71. Planarity Testing in Graph Theory
72. Ramsey Theory and Graph Coloring
73. Graph Isomorphism Problem and Algorithms
74. Tree Algorithms: Lowest Common Ancestor (LCA)
75. Heavy-Light Decomposition for Tree Queries
76. Centroid Decomposition for Trees
77. Euler Tour Technique and Applications
78. Heavy-Light Decomposition in Path Queries
79. Dynamic Trees and Link-Cut Trees
80. Finding Maximum Independent Set in Graphs
81. Graph Representation with Hashing Techniques
82. Minimum Spanning Forest for Disconnected Graphs
83. Depth-First Search (DFS) with Path Compression
84. Two-Pointer Technique in Graphs
85. Euler Tour and Applications in Range Queries
86. Graph Algorithms on Large Datasets
87. Online Algorithms for Graph Problems
88. Randomized Algorithms for Graph Problems
89. Graph Algorithms in Parallel Computing
90. Graph Algorithms with Large-Scale Data
91. Optimizing Space Complexity in Graph Algorithms
92. Graph Algorithms in Geospatial Applications
93. Graph Algorithms for Social Network Analysis
94. Graph Algorithms in Computational Biology
95. Applications of Graph Theory in Cryptography
96. Graph Algorithms for Recommendation Systems
97. Quantum Computing and Graph Algorithms
98. Machine Learning Applications Using Graphs
99. Graph Theory and Game Theory Applications
100. Future Trends in Graph Theory Algorithms and Techniques