Trying to understand Kempe’s algorithm for Graph Coloring

I am trying to understand Kempe’s algorithm to $ k$ -color a planar graph. This is what I understand till now:

Trying to 6-color a planer graph ($ k=6$ )

  1. Find a vertex of degree <= 5 ($ k-1$ )
  2. Remove this vertex
  3. Color the rest of the graph using a recursive call
  4. Put the vertex back, since its degree was at most 5 ($ k-1$ ), we still have at least 1 color left to color this vertex

I understand this procedure but I was curious about the first step: finding a vertex of degree at most $ k-1$ . What would happen if there is no such vertex in the graph? For example, all vertices have a degree $ > k$ . In that case will the algorithm fail?

For what values of $d$ can you reduce $d$-coloring polynomially to $d + 1$ coloring?

For what values of $ d$ can you reduce $ d$ -coloring polynomially to $ d + 1$ coloring?

This is a problem that I’ve been thinking about for a while. Assuming 3-Sat and 3-coloring are NP Complete, for what values of $ d$ am I able to polynomially reduce $ d$ -coloring to $ d+1$ coloring and $ d$ -coloring to $ d-1$ coloring?


NPC PROBLEM minimum sum of vertex coloring

For a graph G and a legal vertex-colouring ψ : V(G)→N of G,

let σψ(G) be the sum of ψ(v),

and set σ(G):=min σψ(G),

where the minimum ranges over all valid vertex colourings of G.

Prove that {(G,k): σ(G)≤ k}∈ NPC.

I thought of reduction from subset-sum but my problem is with the min and not with the sum, I don’t understand how to do a reduction to check the minimum. I got a hint to do a reduction from 3-NAE-SAT but I don’t understand how. would appreciate some help. even some source I can read about this problem if you know about something.

Least Constraining Value heuristic for graph coloring problem

The graph coloring problem involves assigning colors to vertices in a graph, such that no pair of adjacent vertices have the same color. I was given the problem to use least constraining value heuristic to determine the order in which the nodes would be colored.

Image of the given graph

The image shows the graph that must be colored using the set of colors {a,b,c}, using least constraining value heuristic. From my understanding of the LCV heuristic, I am supposed to pick the vertex which eliminates the least amount of colors for its neighbors. We are also given the condition that for tie breaking, we use the smaller numbered node first, and the color ‘a’ first, ‘b’ second and ‘c’ third. Looking at each node, assigning color ‘a’ to vertex 3 only eliminates the possibility of vertex 2 being colored as ‘a’, while all other nodes cause 2 or more changes to their neighbors. Going forward, got the following order. 3a 0a 1a 2b 4c 5b But according to the key, the answer is supposed to be as follows. 0a 1a 2b 3a 4c 5b Could someone please explain what I’m doing wrong?

Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time

We have an undirected simple connected graph with odd number of vertices. We also know the number $ k$ which is actually the closest odd number greater than or equal to $ \Delta$ . (So if $ \Delta$ is even, $ k = \Delta +1$ else $ k=\Delta$ .) i.e $ k$ is the least odd number that is greater than or equal to degrees of all vertices.

We want to find a linear time algorithm that colors the graph with $ k$ colors.

I am very new to graph coloring algorithms. I know that a greedy algorithm is actually linear time and can color the graph with $ \Delta +1$ . But I can’t guarantee I can color it with $ k= \Delta$ when $ \Delta$ is odd. Also, we probably should use all the information the question gives us. i.e using odd number of vertices somehow, but greedy algorithm don’t use this extra information.

How can I solve this?

Coloring an interval graph with weights

I have an interval graph $ G=(V,E)$ and a set of colors $ C=\{c_1,c_2,…,c_m\}$ , when a color $ c_i$ is assigned to a vertex $ v_j$ , we have a score $ u_{ij}\geq 0$ . The objective is to find a coloring of $ G$ with at most $ m$ colors that maximizes the total score (sum of the scores of the vertices).

Do you know about any results in the literature that may help me to find the complexity of this problem?