How to atomically replace a subset of table data
Concurrent reads are not a problem. Writers don't block readers and vice versa in the default READ COMMITTED isolation level. Enclose DELETE and INSERT in a single transaction to make the operation atomic (all applied or nothing).
If there can be multiple transactions trying to write at the same time, that's a game changer. A single transaction protects you from inconsistent updates, but it cannot protect you from race conditions between concurrent transactions: deadlocks.
Say, we have two transactions T1 and T2, and category 'A' has 10 IDs:
T1: DELETE FROM T WHERE category = 'A';
-- starts taking row locks in arbitrary order: id 1,2,3,4,5,6,7 ...
                    T2: DELETE FROM T WHERE category = 'A';
                    -- starts taking row locks in arbitrary order: id 10, 9, 8, ...
T1: wait for T2 to release lock on id 8
                    T2: wait for T1 to release lock on id 7

DEADLOCK.

Postgres detects the deadlock after some time and kills one of the two transactions. (A deadlock error is reported.)
You could switch to SERIALIZABLE transaction isolation. But that's much more expensive and you need to prepare for serialization failures and retry in this case.
Or you can avoid the problem by always deleting rows in identical, deterministic order. Like:
WITH del AS (
   SELECT category, id
   FROM   T
   WHERE  category = 'A'
   ORDER  BY category, id  -- enforce this order in *all* writing queries
   FOR    UPDATE
   )
DELETE FROM T 
USING  del
WHERE  T.category = del.category
AND    T.id = del.id;

But typically, there is a more convenient option. If you have a separate table holding unique categories named, say, cat, you can lock the single parent row in cat with:
SELECT * FROM cat WHERE category = 'A' FOR UPDATE;

and then (in the same transaction) write to category 'A' rows in T at will (still encapsulated in a single transaction to avoid intermediary, inconsistent states being visible).  Of course, all writing queries must follow the same protocol. Then, concurrent transactions will wait for the lock on cat before they write to T and everything is groovy ...
In Postgres 9.4 or later consider FOR NO KEY UPDATE instead:

How to perform conditional insert based on row count?


Concerning:

After each write there will be a read to the adjacent categories.

You are aware of the RETURNING clause, right? No need for a separate read, if you just inserted all rows for a given category. Example:

PostgreSQL multi INSERT…RETURNING with multiple columns