Packing chromatic number for the square lattice is at least 12

This is an add-on page for the manuscript by Jan Ekstein, Jiri Fiala, Premek Holub and Bernard Lidicky. With the assistance of a computer, we have checked that there is no proper packing coloring of the square lattice using 11 colors. The program used to generate all colorings can be downloaded from this page.

Let us briefly remind that we show that it is not possible to color a lattice 15x9 by 11 colors.

The process of checking all the colorings has been split into two steps. The first step is just dividing the problem into many smaller. Then these smaller can be processed in parallel.

The whole procedure is quite straight forward. The description is in the corresponding manuscript which is also available online at arXiv. Let us remark that we have independently written two sets of programs implementing the second step of the procedure. The program available at this web-page was written by Bernard Lidicky in C++; the other program was written by Jan Ekstein in Pascal.

The programs write their output to standard output. We describe the format of inputs and outputs of our programs in detail on this web-page.

All source files, shell script for generating the colorings of a lattice can be downloaded as a tar.gz archive. Outputs and generated inputs have a separate download archive. Program in Pascal can also be downloaded.

Step 1: Generating inputs for parallel processing

Input to our program is a file describing a lattice to color. First line contains minimum and maximum available colors for coloring. In our case we want to use colors from 1 to 11 hence the line is 1 11. The second line contains dimensions of a matrix which should be colored. Our case is 15 times 9 lattice hence the line is 15 9. The last part is a matrix of appropriate size. The entries are colors already in the matrix. Zero denotes a position which must be colored. Hence the initial matrix contains only one non-zero entry - it is the precolored vertex of a color 9.

1 11
15 9
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 9 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0

This input could be put directly to the main coloring procedure but contemporary (year 2009) computers are not able to check all the possibilities in a reasonable time. On the other hand this task is very easy to compute in parallel. Hence first we generate many inputs whose processing does the same job. Note that the following inputs are equivalent to the previous input. We only give first line of the matrix for processing which is full of zeros originally.

Here is an example of a the inputs - there are 10 inputs generated, they differ by the first entry. Together, they cover all possibilities. From second entry on we show only the first line of the input. In the inputs used by the program we actually generate 6498 input files which can be downloaded together with the output files.

1 11
15 9
1 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0  
0 0 0 0 9 0 0 0 0  
0 0 0 0 0 0 0 0 0  
...

2 0 0 0 0 0 0 0 0  

3 0 0 0 0 0 0 0 0  

4 0 0 0 0 0 0 0 0  

5 0 0 0 0 0 0 0 0  

6 0 0 0 0 0 0 0 0  

7 0 0 0 0 0 0 0 0  

8 0 0 0 0 0 0 0 0  

10 0 0 0 0 0 0 0 0  

11 0 0 0 0 0 0 0 0

You may notice that we did not include matrix with 9 in left top corner. It is because of conflict with 9 already placed on [5,5]. Generating of inputs does the same thing but subdivides the task further into 6498 tasks. It turned out that a good condition for stopping dividing the task is usage of first 6 entries or usage of two numbers greater that 3, not counting the 9 on [5,5]. So in total at most 7 vertices are precolored. Output of the generating procedure has the same format as its input. It creates several different files. The files are named according to the sequence of numbers in the first row. Example of input - file 4.2.3.1.2.4.in

1 11
15 9
 4  2  3  1  2  4  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  9  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0

This is not the time consuming part.

Step 2: Checking the colorings

Coloring procedure loads input file and try to color it row by row from left to right. It outputs every time new new coloring record is achieved. This means that the number of zeros is less than ever before. Moreover it outputs currently investigated configuration every 10000000000 configurations. Hence it is possible to check how the program is performing. It is more than a good idea to let several computers to process the input files in parallel.

Some numbers

The computation took 9976077 seconds (115 days) in year 2009 and 43112312093324 configurations were tested.