An algorithm for constructing a weight-controlled subset and its application to graph coloring problem (Q1175054)

There is proposed a new efficient algorithm to solve a weight-controlled subset problem (abbreviated by a \(WSP\)). \(WSP\) is a general form of various combinatorial problems, e.g., the problem of timetables, graph colouring, network flows or Latin squares. There is shown how to check the solvability of a \(WSP\) and to transform it simpler; disproved the conjecture: ``If a \(WSP\) has no solution then it is inconsistent''. The basic properties of the tree derived from a \(WSP\) are used to construct an algorithm for solving a \(WSP\). Gain results are applied to solution of the 4-colour problem. The programs derived from these are given in Fortran.