4

It is Theorem $7$ in this PDF, and there is a proof of the result for the integer lattice and an indication of how to modify it for the rational lattice here.


3

I believe that what you are looking for are the algorithms "Color-Constant-Degree-Graph" and "6-Color-Rooted-Tree" in this paper. The 6 coloring algorithm uses a local algorithm to color the nodes of a graph by having nodes process their color based on their neighbors colors, synchronously. It does this in $O(log^*n)$ time. In case you ...


2

Up to a permutation of the colors there is exactly one such three-coloring. Let ${\mathbb Z}_3$ be the set of colors. The following construction makes use of the cyclic additive structure of ${\mathbb Z}_3$. Assume that we have such a three-coloring of the map. Consider a country $f$ and its $2k$ neighbours. When the country $f$ gets color $0$ its neighbours ...


2

Add a continuous variable $z$ together with the constraints $z \ge x_i$ for all $i\in V$ and minimize $z$. That will induce the solver to use the lowest numbered colors (i.e., $\lbrace 1,\dots, z\rbrace$), and $z$ will be the number of colors used.


2

I will explain Wikipedia's simplest bounds. The lower bound of $n+1$ is by taking $n$ points with $\frac1{\sqrt 2}$ in one coordinate, and $0$ in all others, together with the point which is $\frac{1 + \sqrt{n+1}}{n\sqrt 2}$ in each coordinate. For example, when $n=4$, we get the points $(\frac1{\sqrt2}, 0, 0, 0)$, $(0, \frac1{\sqrt2}, 0,0)$, $(0,0, \frac1{\...


1

Note that connected graph with only one cycle is just tree + 1 extra edge (remove the edge from cycle and you will be left with tree). Chromatic number of tree is 2. Also, in tree, 2 vertices colored same if path length is even. So when you add new edge, if you add it to vertices with same color, then chromatic number will be 3 (odd cycle case), otherwise, ...


1

If you remove edges in the cycle, the graph becomes a union of trees.


1

If you really want a random algorithm that satisfies the weaker guarantee $|E'| \ge \frac{k-2}{k}|E|$ with a good expected runtime, then we can generalize the random approach to the bipartition problem. Choose a random partition $V = V_1 \cup \dots \cup V_k$ by assigning each vertex independently at random to one part; then delete all edges within each part $...


1

A greedy algorithm colors a graph of max degree $\Delta$ in at most $\Delta +1 $ colors. The max degree of a graph with $n$ vertices is $n-1$. So such a graph will take $n$ colors. So we need to solve for $n$ and this will be our upper bound. Further, a graph with $n$ vertices has at most $\frac{n(n-1)}{2}$ edges (equality with the $n$-complete graph). Now ...


1

You want to minimize the number $\chi$ of colors used. You can do this via bisection search for $\chi\in\{1,\dots,|V|\}$ by solving a feasibility problem (no objective) at each step. For each fixed value of $\chi=\hat{\chi}$ during the search, limit the domain of each $x_i$ to $\{1,\dots,\hat{\chi}\}$. If the problem is feasible for $\hat{\chi}$, it is ...


1

In each row we have more red or more blue colored squares. So in at least 21 rows the same color is dominated, say red. So in each of that 21 rows there are at least 3 squares red. Now make 10 sets $S_i$ of rows. Set $S_1$ containing rows which have squares colored like $( \color{red}{r}, \color{red}{r}, \color{red}{r},*,*)$ Set $S_2$ containing rows which ...


1

Let us assume that $k$ is minimal. So a maximum matching $M^*$ of $G$ has precisely $k-1$ edges [why is this]. So letting $M^*$ be an arbitrary maximum matching, let $A=M^* + \{e\}$, for any edge $e$ in $E(G)\setminus M^*$. Then $A$ is a subset of precisely $k$ edges. Next write as $V_A$ the set of vertices covered by $A$. So $A$ is 'almost' a matching; one ...


1

Since there is a unique empty graph of each order $n \geq 1$, I take it that "empty graph" in your question is meant to be shorthand for "the empty graph $E_n$ on $n$ vertices for a positive integer $n$". Since you need at least one color to color the vertices of $E_n$, the chromatic number of $E_n$ is at least $1$. Since there are no ...


Only top voted, non community-wiki answers of a minimum length are eligible