Bipartite graphs: definition, relationship with odd cycles. Vertex coloring: proper col- oring, chromatic number x(G) (!!!), relationship to clique number w(G) and maximum degree A(G). Greedy coloring algorithm and its bound.

Bipartite Graph (!!!)

A graph G is said to be bipartite if we can partition the vertex set into two partitions V₁ and V₂, such that for any edge uv ∈ E(G), u and v belong to different partitions.

Bipartite Graph and Odd Cycles (!!!)

A graph is bipartite if and only if it does not contain any odd cycles (cycles whose length is odd).

Theorem About Odd Cycles

Every closed walk with an odd number of edges contains an odd cycle.

Proper Coloring

Given a graph G, a coloring f : V(G) → {1, 2, …, k} with k colors is said to be a proper coloring of G if no two adjacent vertices share the same color. That is, for every edge (u, v) ∈ E(G), f(u) ≠ f(v).

Chromatic Number (!!!)

The chromatic number χ(G) of a graph G is the minimum number of colors required to obtain a proper coloring of G.

Relationship to Clique Number

For any graph G, χ(G) ≥ ω(G). Every vertex in a clique must receive a different color, so the chromatic number is at least as large as the clique number.

Relationship to Maximum Degree

For any graph G, χ(G) ≤ ∆(G) + 1. This follows directly from the greedy coloring algorithm bound.

Greedy Coloring Algorithm (!!!)

1. Take any ordering of the vertices as v₁, v₂, …, vₙ.

2. Let the available colors be L = {1, 2, …}. 3. For i from 1 to n: color vᵢ with the smallest color in L that is not used by any neighbor vⱼ, where (vᵢ, vⱼ) ∈ E(G), j < i.
   
   Note: it is generally better to order vertices by decreasing degree.

Greedy Coloring Algorithm Bound (!!!)

The greedy coloring algorithm uses at most ∆(G) + 1 colors. A vertex has at most ∆(G) neighbors already colored before it, so even if each neighbor uses a different color, one additional color is always sufficient. ( χ(G) ≤ ∆(G) + 1