Articles of coloring

A Graph as a Union of K forests.

I want to show that a graph G that is a union of k forests has a chromatic number of at most 2k. I have narrowed my problem down to trying to show that any graph G that is a union of n trees has a vertex of degree at most 2n-1, thus I can […]

A plane is colored with three colors. Prove that there exists a right triangle on this plane, having vertices of the same color.

I got stuck with this idea in mind that I could find a shape with all of the vertices connected to each other and all of its angles being 90 degrees. One of such shapes which is not correct is as follows. But, as you can see, it does not work. What is your suggested […]

How many words can be made with $7$ A's, $6$ B's, $5$ C's and $4$ D's with no consecutive equal letters.

I would like to know how many $22$ letter words can be made that have exactly $7$ A’s, $6$ B’s , $5$ C’s and $4$ D’s and have no consecutive letters the same. This problem is clearly equivalent to finding the number of ways to partition $[22]$ into $4$ sets of sizes $7,6,5,4$ such that […]

5-color graph problem

I need to demonstrate that a graph that doesn’t have odd disjunctive circuits is a five color graph. This is indeed for a homework. I need some suggestions on how to approach this problem. Any help is welcomed.

Monochromatic Rectangle of a 2-Colored 8 by 8 Lattice Grid

On a $7 \times 7$ grid of points $(1,1), (1,2), \dots, (7,7)$, show that any coloring of the vertices with two different colors will result in at least one set of four points that form the vertices of a rectangle and are all the same color. With an infinitely large grid we can take 9 […]

Is the Odd-4 graph a unit-distance graph without vertex overlap?

Take the 35 triples of 1-7, from 123 to 567, as vertices. Connect vertices with no shared numbers to get the Odd-4 graph. Let set A be the vertices with 7, set B be the vertices with 6, and let set C be the other vertices. Unit equilateral triangle ABC is now a unit-distance embedding […]

Maximal unit lengths in 3D with $n$ points.

Given $n$ points in 3D space (V), what is the maximal number of unit distance lengths (E) between those points? Here are a few possibilities. Some of them are chromatic spindles. A collection of these best known configurations has been placed at Maximal Unit Lengths in 3D. V — E — figure 4 — 6 […]

Counterexample for $R(4,4) \neq 8$

I try to find a counterexample for $R(4,4)\neq 8$. (R is the Ramsey-number). I drew a graph with 8 vedges and I coloured all edges $(v_i,v_j)$ with $i-j =\pm 2,4,6$ in the same colour (for example in red). But then I’ll find a $K_4$ with $(v_1,v_3,v_5,v_7)$, which is definitely not a counterexample. Perhaps someone can […]

What made the proof of the four color theorem on planes so hard?

What made the proof of the four color theorem for planar graphs so hard? Analogous theorems on different objects (e.g. the torus) were proven long before the planar (spherical) case. Why was the planar case so hard? Or considering that “why” isn’t a very well-defined term in math, what was the obstacle in the proof […]

Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle?

I have a $3$-coloring of $\mathbb{Z}\times\mathbb{Z}$, i.e. a function $f:\mathbb{Z}\times\mathbb{Z}\to\{\color{red}{\text{red}},\color{green}{\text{green}},\color{blue}{\text{blue}}\}$. I have to prove that there is a monochromatic rectangle with its sides being parallel to the axis, i.e. to prove that for some choice of $a,b,c,d\in\mathbb{Z}$ with $a\neq b$ and $c\neq d$, all the points $(a,c),(a,d),(b,c),(b,d)\,$ have the same color. I tried to work […]