# Questions tagged [coloring]

For questions concerned with graph colorings. (This is not for mathematical art.)

1,657 questions
Filter by
Sorted by
Tagged with
4k views

### Graph theoretic proof: For six irrational numbers, there are three among them such that the sum of any two of them is irrational.

Problem. Let there be six irrational numbers. Prove that there exists three irrational numbers among them such that the sum of any two of those irrational numbers is also irrational. I have tried to ...
• 1,171
22k views

### Four color theorem disproof?

My brother in law and I were discussing the four color theorem; neither of us are huge math geeks, but we both like a challenge, and tonight we were discussing the four color theorem and if there were ...
• 651
2k views

### Is Wolfram wrong about unique 3-colorability, or am I just confused?

The illustration on Wolfram's page claims to present a uniquely colorable, triangle-free graph. However, this seems to be blatantly false: the graph has a symmetry with respect to a reflection through ...
• 12.6k
4k views

### How to colour the US map with Yellow, Green, Red and Blue to minimize the number of states with the color of Green

I want to colour the US (only the states) map with Yellow, Green, Red and Blue. I was wondering what would be the lowest number of states with the colour of Green. We can of course use the other ...
• 2,367
17k views

### 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 ...
3k views

### Did the Appel/Haken graph colouring (four colour map) proof really not contribute to understanding?

I hope this isn't off topic - sorry if I'm wrong. In 1976, Kenneth Appel and Wolfgang Haken proved the claim (conjecture) that a map can always be coloured with four colours, with no adjacent regions ...
3k views

### Monochromatic squares in a colored plane

Color every point in the real plane using the colors blue,yellow only. It can be shown that there exists a rectangle that has all vertices with the same color. Is it possible to show that there exists ...
• 20.1k
812 views

### 4 Color Theorem - What am I not seeing??

Let me say first that I am in no way a mathematician. Just slightly interested in mathematics. I think I may have found an exception to the 4 color theorem. I don't claim to be smarter than those who ...
19k views

### Edge-coloring of bipartite graphs

A theorem of König says that Any bipartite graph $G$ has an edge-coloring with $\Delta(G)$ (maximal degree) colors. This document proves it on page 4 by: Proving the theorem for regular ...
• 4,115
2k views

### How many 2-edge-colourings of $K_n$ are there?

I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially ...
• 171
608 views

### We call a coloring of $3$-regular graph with $3$ colors good if for every $3$ edges incident with a vertex ...

Let $G$ be a $3$-regular graph with $n$ vertices. Color each edge with red, blue or yellow. Now, we call a coloring of graph as good if any three edges incident with any vertex have one color or three ...
• 90.3k
604 views

### "Math Lotto" Tickets - finding the minimum winning set

"Math lotto" is played as follows: a player marks six squares on a 6x6 square. Then six "losing squares" are drawn. A player wins if none of the losing squares are marked on his ...
• 3,396
964 views

### Is it possible to uniquely number faces of a hexagonal grid with consecutive numbers?

You have a grid of regular hexagons. The aim of the game is to have each hex contain the numbers 1-6 on its edges. Each edge must also be connected to another edge that has a value one higher and ...
1k views

### 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 ...
• 2,683
6k views

### Edge coloring of the cube

We have a cube and we are coloring its edges. There are three colors available. We say that the two colorings are the same if one can obtain a second by turning cube and permuting colors. Find the ...
• 1,453
621 views

### 5-color coloring game.

Let there be two players, $A$ and $B$, and a map. They now play a game such that: Player $A$ picks a region and player $B$ colors it such that the region is a different color than all adjacent ...
• 796
3k views

• 304
377 views

### AMC 2011 Coloring Problem

A 40 X 40 white square is divided into 1 X 1 squares by lines parallel to its sides. Some of these 1 X 1 squares are coloured red so that each of the 1 X 1 squares, regardless of whether it is ...
• 349
418 views

### Coloring a Generalized Latin Square

Suppose we have an $n \times n$ array, and there is a decomposition $\mathcal{A}$ of its coordinates $a_{i,j}$ into sets $A_m$ as follows: If $a_{i,j} \in A_m$, then $a_{j,i} \in A_m$. So they're ...
• 223