Chapter 75. Fractional Coloring

Ordinary graph coloring assigns exactly one color to each vertex. Fractional coloring relaxes this requirement. Vertices may share colors fractionally, and colors may be distributed in weighted combinations.

This relaxation transforms graph coloring from a discrete combinatorial problem into a continuous optimization problem.

Fractional coloring belongs to linear programming and polyhedral combinatorics as much as to graph theory. It provides sharper bounds, deeper duality theory, and strong connections with probability and optimization.

The fractional chromatic number often behaves more smoothly than the ordinary chromatic number and is easier to analyze mathematically.

75.1 Motivation

Suppose tasks conflict according to a graph.

In ordinary coloring:

• each task receives exactly one time slot,
• adjacent tasks must use different slots.

This creates rigid constraints.

Fractional coloring allows more flexibility.

Instead of assigning a single slot, a task may share several slots proportionally. Over time, each task receives enough total allocation while conflicting tasks avoid simultaneous use.

This corresponds naturally to:

• time sharing,
• bandwidth allocation,
• scheduling,
• probabilistic assignments.

Fractional coloring measures the minimum weighted amount of color needed under this relaxed model.

75.2 Independent Sets

Fractional coloring is built from independent sets.

Recall:

An independent set is a set of pairwise nonadjacent vertices.

In ordinary coloring:

• each color class is an independent set,
• the vertex set is partitioned into independent sets.

Fractional coloring replaces partitions with weighted coverings.

Instead of assigning each vertex to exactly one independent set, we may assign weights to many independent sets simultaneously.

75.3 Fractional Colorings

Let:

denote the family of all independent sets of a graph $G$.

Assign a nonnegative weight:

to every independent set $I\in\mathcal{I}(G)$.

The assignment is a fractional coloring if every vertex $v$ satisfies:

\sum_{I\ni v}w(I)\ge1

Thus each vertex receives total weight at least 1 from independent sets containing it.

The total weight is:

The goal is to minimize this quantity.

75.4 Fractional Chromatic Number

The fractional chromatic number of $G$, denoted:

is the minimum possible total weight of a fractional coloring.

\chi_f(G)=\min\sum_{I\in\mathcal I(G)}w(I)

subject to:

for every vertex $v$.

This is a linear programming problem.

The fractional chromatic number is therefore a continuous relaxation of ordinary coloring.

75.5 Relation to Ordinary Coloring

Every ordinary coloring gives a fractional coloring.

Suppose:

is a proper coloring.

Each color class $V_i$ is independent.

Assign:

for each color class and weight 0 to all other independent sets.

Then every vertex receives total weight exactly 1.

The total weight is:

Therefore:

\chi_f(G)\le\chi(G)

Fractional coloring can only improve upon ordinary coloring.

75.6 Complete Graphs

For the complete graph $K_n$:

• every independent set has size 1,
• each vertex requires weight at least 1.

Thus each vertex must receive its own unit weight.

Therefore:

Hence:

Complete graphs show no difference between fractional and ordinary coloring.

75.7 Bipartite Graphs

A bipartite graph satisfies:

Also:

whenever the graph has at least one edge.

Thus bipartite graphs again show equality.

The distinction between fractional and ordinary coloring becomes interesting in more complicated graphs.

75.8 Odd Cycles

Odd cycles provide the first major difference.

For the cycle:

ordinary coloring gives:

However:

\chi_f(C_{2m+1})=\frac{2m+1}{m}

For example:

Thus fractional coloring lies strictly below ordinary coloring.

This demonstrates how fractional coloring smooths discrete constraints.

75.9 Example: $C_5$

The cycle $C_5$ has five independent sets of size 2:

Assign weight:

to each of these five sets.

Every vertex belongs to exactly two chosen sets, so each vertex receives total weight:

The total weight is:

Hence:

One can show equality holds.

Thus:

75.10 Linear Programming Formulation

Fractional coloring is naturally expressed as a linear program.

Primal Program

Minimize:

subject to:

and:

for every vertex $v$.

This is the standard fractional coloring program.

75.11 Dual Program

Linear programming duality gives a second interpretation.

The dual problem maximizes:

subject to:

for every independent set $I$.

The variables $y_v$ assign weights to vertices.

This dual viewpoint connects fractional coloring with packing problems and stable-set theory.

Duality is one of the major reasons fractional coloring is important.

75.12 Clique Bound

The clique number remains a lower bound:

\omega(G)\le\chi_f(G)\le\chi(G)

Indeed, vertices inside a clique cannot share independent sets. Their total required weight forces at least one unit per clique vertex.

Thus fractional chromatic number lies between clique number and ordinary chromatic number.

75.13 Vertex-Transitive Graphs

Fractional coloring behaves especially cleanly for vertex-transitive graphs.

A graph is vertex-transitive if all vertices are structurally equivalent under automorphisms.

For such graphs:

where:

• $\alpha(G)$ is the independence number.

\chi_f(G)=\frac{|V(G)|}{\alpha(G)}

This formula is exact for many symmetric graphs.

For $C_5$:

so:

75.14 Fractional vs Ordinary Coloring

Fractional coloring behaves more smoothly than ordinary coloring.

Fractional coloring is often easier to estimate and analyze.

However, it loses some combinatorial structure because it allows splitting and averaging.

75.15 Fractional Perfect Graphs

A graph satisfies:

if and only if it is perfect.

Thus perfect graphs may also be characterized through fractional coloring.

Perfect graph theory therefore fits naturally into the fractional framework.

This connection is one reason perfect graphs are central in combinatorial optimization.

75.16 Probabilistic Interpretation

Fractional coloring has a probabilistic interpretation.

Suppose independent sets are chosen randomly according to some probability distribution.

Each vertex should belong to a chosen independent set with probability at least:

Then:

acts like a fractional coloring parameter.

This probabilistic viewpoint is extremely useful in extremal combinatorics.

75.17 Applications

Fractional coloring appears naturally in resource-sharing systems.

Fractional models often reflect practical systems more accurately than rigid discrete assignments.

75.18 Integrality Gap

The difference:

is called an integrality gap.

It measures how much additional cost is created by requiring discrete color assignments rather than fractional sharing.

Large integrality gaps indicate graphs where combinatorial constraints are especially rigid.

Understanding this gap is an important topic in approximation algorithms.

75.19 Fractional Edge Coloring

Edge coloring also has a fractional version.

Instead of matchings partitioning edges discretely, weighted matchings are used.

Fractional edge coloring connects closely with matching polyhedra and network optimization.

These ideas belong to polyhedral combinatorics and linear optimization.

75.20 Summary

Fractional coloring relaxes ordinary graph coloring by allowing weighted combinations of independent sets.

The central parameter is the fractional chromatic number:

\chi_f(G)

which satisfies:

\omega(G)\le\chi_f(G)\le\chi(G)

The main ideas are:

Fractional coloring connects graph theory with optimization, probability, and polyhedral geometry. It provides a smoother and often more tractable version of graph coloring while preserving much of the underlying combinatorial structure.

75.21 Exercises

1. Define a fractional coloring.

2. Define the fractional chromatic number.

3. Prove that:

4. Prove that:

5. Compute $\chi_f(K_n)$.

6. Compute $\chi_f(C_5)$.

7. Explain why:

but

8. Describe the linear programming formulation of fractional coloring.

9. State the dual linear program.

10. Explain the probabilistic interpretation of fractional coloring.

11. Show that bipartite graphs satisfy:

when nonempty.

12. Explain why fractional coloring is easier computationally than ordinary coloring.

13. Define the integrality gap.

14. Explain the relationship between perfect graphs and fractional coloring.

15. Compare ordinary coloring with fractional coloring in scheduling applications.