Advanced Graph Patterns: Classical Problems & Computational Boundaries

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

    Graph Type                          Chromatic Number χ(G)
    ================================================================
    
    Empty graph En (no edges)            χ = 1 (all vertices same color)
    
    Complete graph Kn                    χ = n (all vertices different)
    
    Path graph Pn (n ≥ 2)               χ = 2 (alternate colors)
    
    Cycle Cn (even n)                    χ = 2 (bipartite)
    
    Cycle Cn (odd n)                     χ = 3 (not bipartite)
    
    Complete bipartite Km,n              χ = 2 (bipartite)
    
    Wheel Wn (cycle + center)            χ = 3 (n even) or 4 (n odd)
    
    Petersen graph                       χ = 3
    
    Any planar graph                     χ ≤ 4 (Four Color Theorem)
    
    Any tree                             χ = 2 (trees are bipartite)
    
    Visual example - Triangle (K3):
    
         R           χ(K3) = 3
        / \          
       B---G         R = Red, B = Blue, G = Green
                     Each vertex needs its own color
    
    Visual example - Square (C4):
    
       R --- B       χ(C4) = 2
       |     |
       B --- R       Alternating pattern works

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

    Consider K4, the complete graph on 4 vertices (tetrahedron):
    
         1           This is planar! (can be drawn without crossings)
        /|\
       / | \         Planar embedding:
      /  |  \
     2---+---3           1
      \  |  /          / | \
       \ | /          2--+--3
        \|/            \ | /
         4               4
    
    Every vertex is adjacent to every other vertex.
    Therefore: χ(K4) = 4 (each vertex needs unique color)
    
    The Four Color Theorem says 4 is ALWAYS enough for planar graphs.
    K4 shows that sometimes 4 is NECESSARY.
    
    -------------------------------------------------------------------
    
    The Five Color Theorem is much easier to prove:
    - Every planar graph has a vertex of degree ≤ 5 (Euler's formula)
    - By induction, remove this vertex, 5-color the rest
    - The removed vertex has ≤ 5 neighbors, using ≤ 5 colors
    - If they use all 5 colors... (Kempe chain argument)
    
    Going from 5 to 4 colors requires much more sophisticated analysis.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

/**
 * Check if a graph is 2-colorable (bipartite)
 * Uses BFS to attempt a 2-coloring
 * 
 * Time Complexity: O(V + E)
 * Space Complexity: O(V)
 */
function isBipartite(adjacencyList: number[][]): boolean {
    const n = adjacencyList.length;
    const color: number[] = new Array(n).fill(-1);  // -1 = uncolored
    
    // Handle disconnected graphs
    for (let start = 0; start < n; start++) {
        if (color[start] !== -1) continue;  // Already colored
        
        // BFS from this component
        const queue: number[] = [start];
        color[start] = 0;
        
        while (queue.length > 0) {
            const current = queue.shift()!;
            
            for (const neighbor of adjacencyList[current]) {
                if (color[neighbor] === -1) {
                    // Uncolored: assign opposite color
                    color[neighbor] = 1 - color[current];
                    queue.push(neighbor);
                } else if (color[neighbor] === color[current]) {
                    // Same color as current: odd cycle detected!
                    // Graph is NOT bipartite
                    return false;
                }
                // If different color, that's fine, continue
            }
        }
    }
    
    // Successfully 2-colored all components
    return true;
}
 
/**
 * Returns the 2-coloring if graph is bipartite, null otherwise.
 * The two 'colors' are represented as sets of vertices.
 */
function getBipartition(adjacencyList: number[][]): 
    { setA: number[], setB: number[] } | null {
    
    const n = adjacencyList.length;
    const color: number[] = new Array(n).fill(-1);
    
    for (let start = 0; start < n; start++) {
        if (color[start] !== -1) continue;
        
        const queue: number[] = [start];
        color[start] = 0;
        
        while (queue.length > 0) {
            const current = queue.shift()!;
            
            for (const neighbor of adjacencyList[current]) {
                if (color[neighbor] === -1) {
                    color[neighbor] = 1 - color[current];
                    queue.push(neighbor);
                } else if (color[neighbor] === color[current]) {
                    return null;  // Not bipartite
                }
            }
        }
    }
    
    // Partition vertices by color
    const setA: number[] = [];
    const setB: number[] = [];
    
    for (let v = 0; v < n; v++) {
        if (color[v] === 0) setA.push(v);
        else setB.push(v);
    }
    
    return { setA, setB };
}
 
// Example: Check if a cycle is bipartite
const cycleFour = [[1, 3], [0, 2], [1, 3], [2, 0]];  // C4 - square
const cycleThree = [[1, 2], [0, 2], [0, 1]];         // C3 - triangle
 
console.log(isBipartite(cycleFour));   // true (even cycle)
console.log(isBipartite(cycleThree));  // false (odd cycle)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

/**
 * Greedy graph coloring algorithm
 * 
 * Time Complexity: O(V × Δ) where Δ is max degree
 *                  Or O(V + E) with efficient data structures
 * Space Complexity: O(V + Δ)
 * 
 * Guarantees: Uses at most Δ + 1 colors
 */
function greedyColoring(adjacencyList: number[][]): number[] {
    const n = adjacencyList.length;
    const color: number[] = new Array(n).fill(-1);  // -1 = uncolored
    
    // Process vertices in order 0, 1, 2, ..., n-1
    for (let v = 0; v < n; v++) {
        // Collect colors used by neighbors
        const usedColors = new Set<number>();
        for (const neighbor of adjacencyList[v]) {
            if (color[neighbor] !== -1) {
                usedColors.add(color[neighbor]);
            }
        }
        
        // Find smallest available color
        let c = 0;
        while (usedColors.has(c)) {
            c++;
        }
        
        color[v] = c;
    }
    
    return color;
}
 
/**
 * Greedy coloring with custom vertex ordering
 * Different orderings can produce different numbers of colors!
 */
function greedyColoringWithOrdering(
    adjacencyList: number[][],
    order: number[]
): number[] {
    const n = adjacencyList.length;
    const color: number[] = new Array(n).fill(-1);
    
    for (const v of order) {
        const usedColors = new Set<number>();
        for (const neighbor of adjacencyList[v]) {
            if (color[neighbor] !== -1) {
                usedColors.add(color[neighbor]);
            }
        }
        
        let c = 0;
        while (usedColors.has(c)) {
            c++;
        }
        
        color[v] = c;
    }
    
    return color;
}
 
/**
 * Welsh-Powell algorithm: order vertices by decreasing degree
 * Often produces better results than arbitrary ordering
 */
function welshPowellColoring(adjacencyList: number[][]): number[] {
    const n = adjacencyList.length;
    
    // Sort vertices by degree (descending)
    const verticesByDegree = Array.from({ length: n }, (_, i) => i)
        .sort((a, b) => adjacencyList[b].length - adjacencyList[a].length);
    
    return greedyColoringWithOrdering(adjacencyList, verticesByDegree);
}
 
/**
 * Count the number of colors used
 */
function countColors(coloring: number[]): number {
    return new Set(coloring).size;
}
 
// Example: Compare different orderings on the same graph
//
//     0---1
//     |\  |
//     | \ |
//     |  \|
//     3---2
//
const graph = [
    [1, 2, 3],  // 0
    [0, 2],     // 1
    [0, 1, 3],  // 2
    [0, 2]      // 3
];
 
// Natural order: 0, 1, 2, 3
const coloring1 = greedyColoring(graph);
console.log("Natural order:", coloring1, "Colors used:", countColors(coloring1));
 
// Reverse order: 3, 2, 1, 0
const coloring2 = greedyColoringWithOrdering(graph, [3, 2, 1, 0]);
console.log("Reverse order:", coloring2, "Colors used:", countColors(coloring2));
 
// Welsh-Powell (by degree)
const coloring3 = welshPowellColoring(graph);
console.log("Welsh-Powell:", coloring3, "Colors used:", countColors(coloring3));
 
// Output might be:
// Natural order: [0, 1, 2, 1] Colors used: 3
// Reverse order: [2, 1, 0, 1] Colors used: 3
// Welsh-Powell: [0, 1, 2, 1] Colors used: 3
// 
// Actual χ(graph) = 3 (has triangle 0-1-2 or 0-2-3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

    APPLICATION: Round-Robin Tournament Scheduling
    ================================================
    
    Problem: n teams, each pair must play exactly once.
             Minimize the number of rounds (time slots).
             Each team can only play one game per round.
    
    Model: Complete graph Kn
           - Vertices = teams
           - Edges = games
           - Edge coloring = round assignment
           
    Each round is a "matching" - no vertex appears twice.
    Minimum rounds = χ'(Kn)
    
    For n = 6 teams:
    Δ = 5 (each team plays 5 games)
    n is even, so χ'(K6) = 5
    
    We can schedule all 15 games in just 5 rounds!
    
    Round 1: (1,2), (3,4), (5,6)   - 3 games
    Round 2: (1,3), (2,5), (4,6)   - 3 games
    Round 3: (1,4), (2,6), (3,5)   - 3 games
    Round 4: (1,5), (2,4), (3,6)   - 3 games
    Round 5: (1,6), (2,3), (4,5)   - 3 games
    
    ---------------------------------------------------
    
    For n = 5 teams:
    Δ = 4 (each team plays 4 games)
    n is odd, so χ'(K5) = 5
    
    We need 5 rounds, but only 2 games per round (one team sits out)
    
    This is why sports leagues prefer even numbers of teams!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

/**
 * Simplified register allocation using graph coloring
 * 
 * This demonstrates the core concept:
 * 1. Build an interference graph from variable live ranges
 * 2. Apply graph coloring to assign registers
 * 3. Handle spills when not enough registers available
 */
 
interface LiveRange {
    variable: string;
    start: number;  // First use (line number)
    end: number;    // Last use (line number)
}
 
/**
 * Check if two live ranges overlap (interfere)
 */
function rangesInterfere(a: LiveRange, b: LiveRange): boolean {
    return !(a.end < b.start || b.end < a.start);
    // They interfere if NOT (a ends before b starts OR b ends before a starts)
}
 
/**
 * Build interference graph from live ranges
 * Returns adjacency list indexed by variable names
 */
function buildInterferenceGraph(
    ranges: LiveRange[]
): Map<string, Set<string>> {
    const graph = new Map<string, Set<string>>();
    
    // Initialize empty neighbor sets
    for (const range of ranges) {
        graph.set(range.variable, new Set());
    }
    
    // Check all pairs for interference
    for (let i = 0; i < ranges.length; i++) {
        for (let j = i + 1; j < ranges.length; j++) {
            if (rangesInterfere(ranges[i], ranges[j])) {
                graph.get(ranges[i].variable)!.add(ranges[j].variable);
                graph.get(ranges[j].variable)!.add(ranges[i].variable);
            }
        }
    }
    
    return graph;
}
 
/**
 * Greedy register allocation
 * Returns assignment or null for variables that need spilling
 */
function allocateRegisters(
    interferenceGraph: Map<string, Set<string>>,
    numRegisters: number
): Map<string, number | 'spill'> {
    const assignment = new Map<string, number | 'spill'>();
    const variables = Array.from(interferenceGraph.keys());
    
    // Sort by degree (descending) - handle high-interference vars first
    variables.sort((a, b) => 
        interferenceGraph.get(b)!.size - interferenceGraph.get(a)!.size
    );
    
    for (const variable of variables) {
        // Find registers used by interfering neighbors
        const usedRegisters = new Set<number>();
        for (const neighbor of interferenceGraph.get(variable)!) {
            const reg = assignment.get(neighbor);
            if (typeof reg === 'number') {
                usedRegisters.add(reg);
            }
        }
        
        // Find smallest available register
        let reg = 0;
        while (reg < numRegisters && usedRegisters.has(reg)) {
            reg++;
        }
        
        if (reg < numRegisters) {
            assignment.set(variable, reg);
        } else {
            assignment.set(variable, 'spill');  // Must use memory
        }
    }
    
    return assignment;
}
 
// Example: Simple code with variables a, b, c, d, e
const liveRanges: LiveRange[] = [
    { variable: 'a', start: 1, end: 5 },
    { variable: 'b', start: 2, end: 6 },
    { variable: 'c', start: 3, end: 4 },
    { variable: 'd', start: 5, end: 8 },
    { variable: 'e', start: 7, end: 10 },
];
 
const interference = buildInterferenceGraph(liveRanges);
console.log("Interference graph:");
for (const [v, neighbors] of interference) {
    console.log(`  ${v} interferes with: ${[...neighbors].join(', ')}`);
}
 
const allocation = allocateRegisters(interference, 3);
console.log("\nRegister allocation (3 registers):");
for (const [v, reg] of allocation) {
    console.log(`  ${v} → ${reg === 'spill' ? 'MEMORY (spill)' : 'R' + reg}`);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

/**
 * DSatur (Saturation Degree First) Coloring Algorithm
 * 
 * Dynamically selects the next vertex to color based on:
 * 1. Maximum saturation degree (number of differently colored neighbors)
 * 2. Ties broken by maximum uncolored degree
 * 
 * Often produces near-optimal colorings in practice.
 * 
 * Time Complexity: O(V² × Δ) - can be optimized with priority queues
 * Space Complexity: O(V × Δ)
 */
function dsaturColoring(adjacencyList: number[][]): number[] {
    const n = adjacencyList.length;
    const color: number[] = new Array(n).fill(-1);
    const saturation: number[] = new Array(n).fill(0);
    const neighborColors: Set<number>[] = Array.from(
        { length: n }, 
        () => new Set()
    );
    
    let colored = 0;
    
    while (colored < n) {
        // Find uncolored vertex with highest saturation
        // (ties broken by highest degree)
        let bestVertex = -1;
        let bestSaturation = -1;
        let bestDegree = -1;
        
        for (let v = 0; v < n; v++) {
            if (color[v] !== -1) continue;  // Already colored
            
            const sat = neighborColors[v].size;
            const deg = adjacencyList[v].filter(u => color[u] === -1).length;
            
            if (sat > bestSaturation || 
                (sat === bestSaturation && deg > bestDegree)) {
                bestVertex = v;
                bestSaturation = sat;
                bestDegree = deg;
            }
        }
        
        // Assign smallest available color
        let c = 0;
        while (neighborColors[bestVertex].has(c)) {
            c++;
        }
        color[bestVertex] = c;
        colored++;
        
        // Update saturation of neighbors
        for (const neighbor of adjacencyList[bestVertex]) {
            if (color[neighbor] === -1) {
                neighborColors[neighbor].add(c);
            }
        }
    }
    
    return color;
}
 
/**
 * Recursive Largest First (RLF) Algorithm
 * 
 * Builds independent sets (single-color classes) one at a time.
 * For each color, greedily adds vertices that don't conflict.
 */
function rlfColoring(adjacencyList: number[][]): number[] {
    const n = adjacencyList.length;
    const color: number[] = new Array(n).fill(-1);
    const uncolored = new Set<number>(Array.from({ length: n }, (_, i) => i));
    
    let currentColor = 0;
    
    while (uncolored.size > 0) {
        // Build an independent set for this color
        const candidates = new Set(uncolored);
        
        while (candidates.size > 0) {
            // Find candidate with most uncolored non-neighbors in candidates
            // (or most neighbors in already-colored vertices)
            let bestVertex = -1;
            let bestScore = -1;
            
            for (const v of candidates) {
                // Score: number of already-colored neighbors (prefer high)
                const score = adjacencyList[v].filter(u => color[u] !== -1).length;
                if (score > bestScore) {
                    bestScore = score;
                    bestVertex = v;
                }
            }
            
            // If all scores are 0, pick highest degree in candidates
            if (bestScore === 0) {
                for (const v of candidates) {
                    const deg = adjacencyList[v].filter(u => candidates.has(u)).length;
                    if (deg > bestScore) {
                        bestScore = deg;
                        bestVertex = v;
                    }
                }
            }
            
            // Assign color
            color[bestVertex] = currentColor;
            uncolored.delete(bestVertex);
            candidates.delete(bestVertex);
            
            // Remove neighbors from candidates (they can't have this color)
            for (const neighbor of adjacencyList[bestVertex]) {
                candidates.delete(neighbor);
            }
        }
        
        currentColor++;
    }
    
    return color;
}
 
// Compare algorithms on the same graph
const testGraph = [
    [1, 2, 3],
    [0, 2, 4],
    [0, 1, 3, 4],
    [0, 2, 5],
    [1, 2, 5],
    [3, 4]
];
 
console.log("Greedy:", countColors(greedyColoring(testGraph)), "colors");
console.log("DSatur:", countColors(dsaturColoring(testGraph)), "colors");
console.log("RLF:", countColors(rlfColoring(testGraph)), "colors");
 
function countColors(coloring: number[]): number {
    return new Set(coloring).size;
}