<figure><img src="image_1.png" /></figure>

HAL
open science

# A note on the complexity of the chromatic number problem

Eugene Lawler

<figure><img src="image_2.png" /></figure>

## To cite this version:

Eugene Lawler. A note on the complexity of the chromatic number problem. [Research Report] IRIA-RR-204, IRIA. 1976, pp.8. hal-04716389

HAL Id: hal-04716389

https://inria.hal.science/hal-04716389v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Inv-02532 RR204

IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B.P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_4.png" /></figure>

A NOTE
ON THE COMPLEXITY
OF THE
CHROMATIC NUMBER PROBLEM

Eugène LAWLER

Rapport de Recherche N° 204
Décembre 1976
# A NOTE ON THE COMPLEXITY OF THE CHROMATIC NUMBER PROBLEM

E.L. Lawler

IRIA

University of California
Berkeley, CA (U.S.A.)

## Abstract :

The chromatic number problem can be solved by an algorithm with worst-case running time of $O(mn(1 + \sqrt[3]{3})^n)$, where *m* is the number of arcs of the graph and *n* is the number of nodes. Three colorability can be tested in $O(mn3^{n/3})$ and four colorability in $O(m+n)2^n)$ time.

## Résumé :

Le problème du nombre chromatique peut être résolu en un temps $O(mn(1 + \sqrt[3]{3})^n)$, où *n* est le nombre d'arcs du graphe et *m* est le nombre de nœuds. On peut tester si un graphe est coloriable en 3 couleurs en un temps $O(mn 3^{n/3})$ et en un temps $O(m + n)2^n)$ pour quatre couleurs.
# A NOTE ON THE COMPLEXITY
OF THE CHROMATIC NUMBER PROBLEM

E.L. LAWLER

IRIA

Rocquencourt, FRANCE

and

University of California

Berkeley, CA, USA

## ABSTRACT

The chromatic number problem can be solved by an algorithm with worst-case running time of $O(mn(1 + {}^3\sqrt{3})^n)$, where m is the number of arcs of the graph and n is the number of nodes. Three colorability can be tested in $O(mn^{3n/3})$ time and four colorability in $O(m+n)2^n)$ time.

## RESUME

Le problème du nombre chromatique peut être résolu en un temps $O(mn(1 + {}^3\sqrt{3})^n)$, où m est le nombre d'arcs du graphe et n est le nombre de noeuds. On peut tester si un graphe est colorable en 3 couleurs en un temps $O(mn^{3n/3})$ et en un temps $O(m+n)2^n)$ pour quatre couleurs.
# I - INTRODUCTION

It is well-known that the chromatic number problem is NP-complete. In fact, even the problem of determining the chromatic number of an arbitrary graph to within a given factor $r < 2$ has also been shown to be NP-complete [5]. It follows that there is very little prospect of finding and efficient, i.e. polynomial-bounded, algorithm for the general problem, although some special cases can be solved efficiently, e.g. [6].

A number of algorithms have been proposed [1, 2, 3, 7, 10], yet there appears to be no information in the literature concerning nontrivial upper bounds on the complexity of the problem. In this note we show, by very simple arguments, that the problem can be solved by an algorithm with worst-case running time of $O(mn(1 + \sqrt[3]{3})^n)$, where m is the number of arcs in the graph and n is the number of nodes. (Note : $1 + \sqrt[3]{3} \approx 2.445$.)

# 2 - DEFINITIONS

Let $G(N,A)$ be a graph, with node set $N$ and arc set $A$. A *stable* subset of $G$ is a subset $S \subseteq N$ such that no two nodes in $S$ are adjacent in $G$. A *k-coloring* of $G$ is a partition of $N$ into $k$ stable subsets. If there exists such a partition, $G$ is said to be *k-colorable*. The *chromatic number* of $G$ is the least value of $k$ such that $G$ is $k$-colorable.

Let $N'$ be an arbitrary subset of the nodes of $G$. The subgraph of $G$ *induced on* $N'$ has $N'$ as its node set and $A'$ as its arc set, where $A'$ contains all arcs of $A$, both ends of which are incident to nodes in $N'$. We let $\chi(N')$ denote the chromatic number of the subgraph induced on $N'$.

# 3 - A RECURSIVE COMPUTATION

A stable subset $S$ is **maximal** if $S$ is not a proper subset of any other stable subset $S'$. It is asserted that if a graph is $k$-colorable, there is a partition of its node set into $k$ stable subsets, where at least one of the stable subsets is maximal. It follows that if $N'$ is nonempty, there exists
a maximal stable subset S of the subgraph induced on N', such that

$$ \chi(N') = 1 + \chi(N'-S). $$

There are a finite number of maximal stable subsets S of the induced subgraph. By minimizing over them we obtain

$$ \left. \begin{array}{l} \chi(N') = 1 + \min_{S \subseteq N'} \{\chi(N'-S) : N' \neq \emptyset\} \\ \\ \chi(\emptyset) = 0 \end{array} \right\} (*) $$

These equations, in fact, represent the essential ideas behind various computational procedures which have been proposed for the chromatic number problem. See especially [3, 10].

## 4 - COMPLEXITY ESTIMATE

We shall estimate the running time required to solve equations (*) for all $N' \subseteq N$, in the worst case.

Suppose, for fixed N', we have already found $\chi(N'')$, for all proper subsets $N'' \subseteq N$. The time required to compute $\chi(N')$ is then proportional to the number of maximal stable subsets of the subgraph induced on N', plus the time required to generate them. We make use of two results.:

1. The number of maximal stable subsets of a graph on r nodes does not exceed $3^{r/3}$ [7].

2. There exists an algorithm for generating all maximal stable subsets of an r-node graph in time $O(mrK)$, where K is the number of maximal stable subsets [9]. (See also [8]).

It follows that the time required to compute $\chi(N')$ is bounded by a function of $O(mr3^{r/3})$. Summing over all $N' \subseteq N$ and invoking the binomial theorem, we find that the overall running time required to solve equations (*) is bounded by a function of order
$$ \sum_{r=0}^{n} \binom{n}{r} mr^3 r^{3/3} < mn \sum_{r=0}^{n} \binom{n}{r} 3^{r/3} = mn(1 + \sqrt[3]{3})^n. $$

This yields the desired result.

## 5 - REFINEMENTS OF COMPUTATION

There are certain refinements of the recursive computation which one might hope to use to reduce the complexity estimate. For example, it is easily shown that one need minimize over only those stable subsets S which contain an arbitrarily chosen node in N'. There can be no more than $3^{(r-d-1)/3}$ such maximal stable subsets, where d is the degree of the chosen node in the induced subgraph.

If N' is a nonempty stable subset of G, then of course $\chi(N') = 1$. If N' is not a stable subset of G, and the subgraph induced on N' is bipartite, then $\chi(N') = 2$. If the subgraph induced on N' is nonbipartite and contains a node i with degree less than 3, then $\chi(N') = \chi(N' - \{i\})$.

The author has attempted to invoke all the above observations, and others, in an attempt to reduce the bound on the running time. He has been unsuccessful, other than in obtaining a reduction by a constant linear scale factor. Other investigators are challenged to do better.

## 6 - OTHER RESULTS

To test a graph for three-colorability, one can generate all maximal stable subsets and then check the induced subgraph on each complementary set of nodes for bipartiteness. It follows that such a test can be made in $O(mn\sqrt[3]{3})$ time.

To test a graph for four-colorability, one can form all $2^n$ partitions of the graph into two sets and check each induced subgraph for bipartiteness. It follows that such a test can be made in $O((m+n)2^n)$ time.
The author knows of no test for five-colorability with a bound better than that for the general chromatic number problem.

Finally, it should be mentioned that all of the running time bounds stated in this note can be easily be shown to apply to "strong" coloring of hypergraphs [4].
REFERENCES

[1] J. R. BROWN, "Chromatic Scheduling and the Chromatic Number Problem", Management Science, 19 (1972) 456-463.

[2] D.G. CORNEIL and B. GRAHAM, "An Algorithm for Determining the Chromatic Number of a Graph", SIAM J. Comput., 2 (1973) 311-318.

[3] N. CHRISTOFIDES, "An Algorithm for the Chromatic Number of a Graph", Computer J., 14 (1971) 38-39.

[4] D. de WERRA, "How to Color a Graph", Combinatorial Programming : Methods and Applications, B. Roy, ed., D. Reidel Publ. Co., Dordrecht, Holland, 1975, pp. 305-325.

[5] M. R. GAREY and D.S. JOHNSON, "The Complexity of Near-Optimal Graph Coloring", Journal ACM, 23 (1976) 43-49.

[6] F. GAVRIL, "Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph", SIAM J. Comput., 1 (1972) 180-187.

[7] D.W. MATULA, G. MARBLE and J.D. ISAACSON, "Graph Coloring Algorithms", Graph Theory and Computing, R.C. Read, ed., Academic Press, New York, 1972, pp. 109-122.

[8] G.D. MULLIGAN and D.G. CORNEIL, "Corrections to Bierstone's Algorithm for Generating Cliques", Journal ACM, 19 (1972) 244-247.

[9] S. TSUKIYAMA, M. IDE, H. ARUJOSHI, and H. OZAKI, "A New Algorithm for Generating all the Maximal Independent Sets", unpublished manuscript.

[10] C.C. WANG, "An Algorithm for the Chromatic Number of a Graph", Journal ACM, 21 (1974) 385-391.