Dear Tomasz,

I suggest you to see links and attached files on topic.

-interval vertex-coloring of a graph with forbidden colors - Science Direct

https://www.sciencedirect.com/science/article/pii/.../pdf?...

-Chap 7.PDF

compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%207.PDF

-Solution outlines. (A graph is k-critical if its chromatic number equals k ...

https://www.mscs.dal.ca/~janssen/4115/assignment/Solutions2.pdf

-GRAPHS WITH LARGE GIRTH AND LARGE CHROMATIC NUMBER ...

math.uchicago.edu/~may/REU2016/REUPapers/Tsui.pdf

-A Reduction based Method for Coloring Very Large Graphs - IJCAI

https://www.ijcai.org/proceedings/2017/0073.pdf

-Edge-weightings and the chromatic number - Department of ...

mathematics.ceu.edu/sites/mathematics.ceu.../corypalmerthesis.pdf

-Chromatic Number -- from Wolfram MathWorld

mathworld.wolfram.com › ... › Wolfram Language Commands

Best regards

Dear Tomasz Mazurkiewicz,

You can study the relation between the chromatic number and the clique number. Also, try to employ the following bound it will help you

$$\lambda_1 \geq \chi - 1$$

where $\lambda_1$ is the spectral radius of the graph.

Thank you for both replies.

Mohamed-Mourad Lafifi: I've already seen most of this link, but did not find exactly what I was actually looking for.

Mohammad Issa Sowaity: I wanted to use maximal clique, but there exist a family of graphs (https://en.wikipedia.org/wiki/Mycielskian) where this approach probably won't be efficient.

I might have not stated it directly in the question, but I want a set of vertices to be the least numerous.

If you are looking for some kind of algorithm, you could try with the most primitive one.

1. determine the chromatic number of a graph,

2. delete one vertex from the graph

3. determine the chromatic number of obtained graph

4. If the chromatic number is reduced, then you have found the vertex.

5. if not try to remove another vertex from original one.

There are several coloring algorithms you can choose. This primitive algorithm is very inefficient, but could be used to compare to a method you find or invent.

Finding "critical" nodes or edges is hard for both NP and co-NP. So any exact algorithm for your problem is going to take exponential time in the worst case. But there might exist an algorithm that works reasonably well in practice... depending on the structure of your instances.

@Adam N. Letchford: do you know any algorithm that address this problem?

The only paper I know that describes an exact algorithm for a problem like this is this one.

Article Finding the Chromatic Number by Means of Critical Graphs.

For small graphs, find the vertex with high degree, elimínate it. For others Article Finding the Chromatic Number by Means of Critical Graphs.