PostGIS functions for map coloring

CREATE OR REPLACE FUNCTION adjacency_list(table_name regclass, user_name text) RETURNS void AS $$
BEGIN
    EXECUTE format('DROP TABLE IF EXISTS %s_adjacency_list;
                    CREATE TABLE %s_adjacency_list AS
                    SELECT DISTINCT a.cartodb_id,
                    array_agg(b.cartodb_id) over (PARTITION BY a.cartodb_id) AS adjacent,
                    count(b.*) over (PARTITION BY a.cartodb_id) AS valence,
                    0 AS color
                    FROM %s a,
                         %s b
                    WHERE st_intersects(a.the_geom, b.the_geom)
                    ORDER BY valence DESC,
                             a.cartodb_id ASC;
                    SELECT CDB_CartoDBFyTable(''' || user_name || ''',''' || table_name || '_adjacency_list'');', table_name, table_name, table_name, table_name);
END
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION greedy_coloring(table_name regclass, user_name text) RETURNS void AS $$
    DECLARE
        item RECORD;
        current_color int = 1;
        cc int;
        guard int;
    BEGIN
        PERFORM adjacency_list(table_name, user_name);
        EXECUTE format('SELECT COUNT(*) FROM %s_adjacency_list WHERE color = 0', table_name) INTO guard;
        WHILE guard > 0 LOOP
            EXECUTE format('UPDATE %s_adjacency_list SET color = $1 WHERE cartodb_id = (SELECT cartodb_id FROM %s_adjacency_list WHERE color = 0 ORDER BY cartodb_id ASC LIMIT 1);', table_name, table_name) USING current_color;
            FOR item IN EXECUTE format('SELECT * FROM %s_adjacency_list WHERE color = 0', table_name) LOOP
                EXECUTE format('SELECT COUNT(*) FROM %s_adjacency_list WHERE color = $1 AND $2 = ANY(adjacent)', table_name) INTO cc USING current_color, item.cartodb_id;
                IF cc = 0 THEN
                    EXECUTE format('UPDATE %s_adjacency_list SET color = $1 WHERE cartodb_id = $2;', table_name) USING current_color, item.cartodb_id;
                END IF;
            END loop;
            current_color = current_color + 1;
            EXECUTE format('SELECT COUNT(*) FROM %s_adjacency_list WHERE color = 0', table_name) into guard;
        END loop;
    END;
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION kempe(table_name regclass, user_name text) RETURNS void AS $$
DECLARE
    item RECORD;
    cc int;
    count int = 1;
    d int;
    temp_cartodb_id int;
    guard int;
BEGIN
    PERFORM adjacency_list(table_name, user_name);
    EXECUTE format('DROP TABLE IF EXISTS %s_temp', table_name);
    EXECUTE format('CREATE TABLE %s_temp (cartodb_id integer, ord integer);', table_name);
    EXECUTE format('SELECT COUNT(*) FROM %s_adjacency_list WHERE valence < 5 AND valence > 0', table_name) INTO guard;
    WHILE guard > 0 LOOP
        EXECUTE format('SELECT cartodb_id FROM %s_adjacency_list WHERE valence < 5 AND valence > 0 ORDER BY valence DESC LIMIT 1', table_name) into temp_cartodb_id;
        EXECUTE format('INSERT INTO %s_temp (cartodb_id, ord) VALUES ($1, $2)', table_name) USING temp_cartodb_id, count;
        count = count + 1;
        EXECUTE format('UPDATE %s_adjacency_list SET valence = 0 WHERE cartodb_id = $1', table_name) USING temp_cartodb_id;
        FOR item IN EXECUTE format('SELECT * FROM %s_adjacency_list WHERE $1 = ANY(adjacent)', table_name) USING temp_cartodb_id LOOP
            EXECUTE format('UPDATE %s_adjacency_list SET valence = valence - 1 WHERE cartodb_id = $1', table_name) USING item.cartodb_id;
        END LOOP;
    EXECUTE format('SELECT COUNT(*) FROM %s_adjacency_list WHERE valence < 5 AND valence > 0', table_name) INTO guard;
    END LOOP;

    EXECUTE format('UPDATE %s_adjacency_list set valence = array_length(adjacent, 1)', table_name);
    EXECUTE format('UPDATE %s_adjacency_list set color = 0', table_name);

    FOR item IN EXECUTE format('SELECT * FROM %s_temp ORDER BY ord DESC', table_name) LOOP
        EXECUTE format('SELECT COUNT(*) FROM %s_adjacency_list WHERE color != 0 AND $1 = ANY(adjacent)', table_name) INTO cc USING item.cartodb_id;
            IF cc = 0 THEN
                EXECUTE format('UPDATE %s_adjacency_list SET color = 1 WHERE cartodb_id = $1', table_name) USING item.cartodb_id;
            ELSE
                EXECUTE format('select (array_agg(elements))[1]
                                from (
                                  select unnest(array[1, 2, 3, 4, 5])
                                  except
                                  SELECT unnest(ARRAY_AGG(color)) FROM %s_adjacency_list WHERE color != 0 AND $1 = ANY(adjacent)
                                ) t (elements)', table_name) INTO d USING item.cartodb_id;
                EXECUTE format('UPDATE %s_adjacency_list SET color = $1 WHERE cartodb_id = $2', table_name) USING d, item.cartodb_id;
            END IF;
    END LOOP;
    EXECUTE format('DROP TABLE IF EXISTS %s_temp', table_name);
END;
$$ LANGUAGE plpgsql;

If you're looking to make these function work on tables with 100k+ shapes in a reasonable time I suggest add some indexes. Go through and add the standard index for cartdodb_id and valence for kemp/for greedy I added a (color, cartdodb_id). For kemp you will also want an index on adjacent I had to change the clauses "$1 = ANY(adjacent)" to "ARRAY[$1] <@ adjacent" for it to use the index. For greedy, which is much faster in my case, I made a special index on color and adjacent which may not be necessary. I simply declared a max_id int, and set it to max(cartodb_id) + 1 and then made a column adjacent_color set to adjacent || (color + max_id) then replaced "color = $1 AND $2 = ANY(adjacent)" with "array[$1, $2] <@ adjacent_color" where $1 is now current_color + max_id. Then made sure to update adjacent_color when you update color in the next statement. With the indexes these queries were several hundred times faster in my case.

Happy mapping!