Skip to main content

Questions tagged [coloring]

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

Filter by
Sorted by
Tagged with
97 votes
6 answers
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 ...
Arpon Basu's user avatar
  • 1,171
42 votes
6 answers
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 ...
Doktor J's user avatar
  • 651
34 votes
1 answer
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 ...
Jakub Konieczny's user avatar
27 votes
1 answer
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 ...
Sina Babaei Zadeh's user avatar
25 votes
4 answers
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 ...
user avatar
21 votes
1 answer
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 ...
user avatar
20 votes
2 answers
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 ...
Amr's user avatar
  • 20.1k
19 votes
3 answers
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 ...
Tyler_Hutchins's user avatar
19 votes
4 answers
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 ...
Klaus's user avatar
  • 4,115
17 votes
2 answers
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 ...
Clum's user avatar
  • 171
17 votes
2 answers
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 ...
nonuser's user avatar
  • 90.3k
15 votes
2 answers
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 ...
Asher2211's user avatar
  • 3,396
15 votes
3 answers
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 ...
Jonathan Van Buren's user avatar
15 votes
1 answer
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 ...
peterh's user avatar
  • 2,683
14 votes
3 answers
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 ...
xan's user avatar
  • 1,453
14 votes
1 answer
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 ...
blademan9999's user avatar
13 votes
3 answers
3k views

Intersecting Odd Cycles, Chromatic Number, and the Subgraph $K_5$

Consider a graph $G$ such that every pair of odd cycles in G intersect. Then $\chi(G) \le 5$. Furthermore, $\chi(G) = 5$ implies $K_5 \subset G $. Here is the proof of the first claim: Let $C\...
Three's user avatar
  • 852
13 votes
2 answers
450 views

Graph theory partitioning game

Players Ruby and Bob are given an undirected graph and a number $N$. First Ruby colors $N$ vertices red, then Bob colors $N$ vertices blue (they must be distinct from Ruby's choices). Afterward, all ...
George Hoqqanen's user avatar
12 votes
1 answer
2k views

Why is this proof for the four color theorem considered wrong?

I'd like to think I found a proof for the four color theorem, but I also know that it took far smarter people than me a computer simulation to prove. Still, I don't see why this logic should be flawed....
Nautilus's user avatar
  • 247
12 votes
4 answers
7k views

Painting chess board

The task is to paint each of the $64$ squares on a chess board either blue or red. I need to find the number of distinct ways this can be done given that any $2\times 2$ square on the board has two ...
Quark's user avatar
  • 1,021
12 votes
1 answer
23k views

Question about the proof that 'A graph with maximum degree at most k is (k + 1) colorable

I'm trying to follow the MIT introductory mathematics for cs course. In the reading on graph theory, the proof that a graph with maximum degree at most k is (k + 1) colorable is given as follows: ...
mallardz's user avatar
  • 245
12 votes
2 answers
536 views

How to color a board such that each square has exactly two neighbors of the opposite color

Let $m≥2$, $n≥2$ integers. We want to color the squares of an $m × n$ board with black and white so that each square has exactly two neighbors of the other color. Determine all the values ​​of $m$ and ...
Qqq's user avatar
  • 255
12 votes
1 answer
4k views

Upper bound on $\chi(G)$ for a triangle-free graph

I'm struggling with the following question; For every graph $G$ such that $K_3 \not\subseteq G$ (i.e. $G$ does not contain a triangle), prove that $\chi(G) \leq 2\sqrt{n} +1$ (where $\chi(G)$ ...
rm95's user avatar
  • 341
12 votes
0 answers
563 views

Example of graph with strange property

The question is now also published in MathOverflow (here). Note: Whenever I mention a coloring of a graph I'm referring to a proper coloring over its vertices using the least amount of colors. ...
Alma Arjuna's user avatar
  • 3,821
11 votes
3 answers
12k views

the Nordhaus-Gaddum problems for chromatic number of graph and its complement

Is there any relation between the chromatic number of a graph $G$ and its complement $G'$ that are always true? I saw these ones: $\chi(G)\chi(G')\geq n$ and $\chi(G)+\chi(G')\geq 2n$, but I'm not ...
Abd's user avatar
  • 111
11 votes
3 answers
14k views

Chromatic index of a complete graph

Looking to show that $\forall n \in \mathbb{N}$ $$\chi^{'}(K_{2n+2})=\chi^{'}(K_{2n+1})=2n+1$$ I'm trying to construct a colouring of the edges of $K_{2n+1}$ that leaves colour $i$ missing at vertex ...
John Fernley's user avatar
  • 1,228
11 votes
2 answers
6k views

Graph theory: Prove $k$-regular graph $\#V$ = odd, $\chi'(G)> k$

I'm looking to prove that any $k$-regular graph $G$ (i.e. a graph with degree $k$ for all vertices) with an odd number of points has edge-colouring number $>k$ ($\chi'(G) > k$). With Vizing, I ...
FreshmanMath's user avatar
11 votes
1 answer
3k views

How many ways to colour a $4 \times 4$ grid using four colours subject to three constraints

In how many ways can a $4 \times 4$ square grid be coloured using four different colours so that no colour is repeated in any row, column, or along the two main diagonals. For clarity, one valid ...
omegadot's user avatar
  • 11.8k
11 votes
2 answers
481 views

A special chess board

Consider a special $n\times n$ chess board such that each $1\times 1$ square is ether black or white. We know that every $1\times 1$ square has exactly one white adjacent square (two squares are ...
Pet123's user avatar
  • 1,252
11 votes
1 answer
1k views

On the four and five color theorems

The five color theorem for planar maps is considerably easier to prove than the four color theorem. The essential part of the proof is the Kempe-Heawood swap: given coloring of a map, choose two ...
DVD's user avatar
  • 1,157
11 votes
1 answer
403 views

Coloring of positive integers

Suppose $f:\mathbb{Z}^+\longrightarrow X$ is a function, with $X$ a finite set. Is it true that there are $a,b\in\mathbb{Z}^+$ such that $f(a)=f(b)=f(a+b)$.
gamel's user avatar
  • 317
11 votes
0 answers
456 views

Number of sets of vertices whose union of neighbours contains exactly $k$ vertices

Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows: For example, $g$ for $n=3$: If I ...
concat's user avatar
  • 303
10 votes
3 answers
5k views

Four colour theorem in $3$ dimensions?

There is, of course the 4 colour theorem, which has been proven - every map can be coloured in just 4 colours. However, has anything been examined in $3$ dimensions? By that, I mean how many ...
Tim's user avatar
  • 520
10 votes
1 answer
6k views

Inequality between chromatic number and number of edges of a graph

I have not been able to find a proof to the statement that if a graph $G$ has $\chi(G)=k$, then it must have at least $\binom{k}{2}$ edges. Would you be able to show me a simple proof?
Aria Fitzpatrick's user avatar
10 votes
2 answers
1k views

$n$ lines in a plane, proper coloring of intersection points with just 3 colors

Draw $n$ lines in a plane so that there are no parallel lines and there are no three lines passing through the same point. Each intersection point is colored red, green or blue. Prove that it is ...
Saša's user avatar
  • 16k
10 votes
2 answers
1k views

Explicit graphs with large chromatic number and girth

It is well known that there exist graphs with large chromatic number and girth. More precisely, for any $k$ and $l$, there exists a graph $G$ such that $\chi(G) > k$ (where $\chi$ denotes the ...
Jakub Konieczny's user avatar
10 votes
3 answers
378 views

What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?

Also asked on MO: What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?. Consider the set $X = \{1,2,3,\dots,n\}$. Define the collection of all $4$-subsets of $X$ by $$\mathcal A=\{...
ArtOfProblemSolving's user avatar
10 votes
1 answer
1k views

Probability that a random edge coloring of the complete graph is proper

Suppose we color the edges $\{1,\ldots, {n \choose 2}\}$ of the complete graph on $n$ vertices with $m$ colors each edge being assigned a color picked uniformly at random from $\{1,\ldots, m\}.$ I ...
Jernej's user avatar
  • 5,022
10 votes
0 answers
587 views

Edge Coloring of Kneser Graphs

Kneser graphs $KG(n, k)$ are well known: the vertices are all $k$-subsets of $\{1,2,\dotsc,n\}$ with two sets connected iff they are disjoint. If the graph is odd (i.e., has an odd number of vertices) ...
stan wagon's user avatar
  • 1,663
9 votes
2 answers
699 views

Intuition behind the "large but finite search space" of the proof of the four colour theorem?

I know the four colour theorem was solved by a computer checking a large number of cases. What I don't understand is why there are only a large but finite number of cases. It seems like there should ...
Seamus's user avatar
  • 4,035
9 votes
2 answers
24k views

How is the graph coloring problem NP-Complete?

An NP-Complete problem can be checked efficiently, but has no known way of being solved in polynomial time. Then, how is the graph coloring problem (http://en.wikipedia.org/wiki/...
David Faux's user avatar
  • 3,435
9 votes
2 answers
470 views

Complete graphs in the plane with colored edges where an edge don't cross edges with same color

The maximal number of nodes in a complete planar graph is $4$. Suppose that the edges of the graph can be chosen with $m$ different colors and that edges with different colors are allowed to cross ...
Lehs's user avatar
  • 13.9k
9 votes
1 answer
19k views

Coloring a $3\times n$ board using $3$ colors

I have been reading about Combinatorial Material for a while now. I also solved a few examples. However am stuck at this one. Find the total number of ways a $3 \times n$ board can be painted ...
guthik's user avatar
  • 429
9 votes
2 answers
131 views

Coloring a $9\times9$ Board

Consider a $9 \times 9$ board, and we want to paint each of the $81$ squares either white or black. There are $64$ $2\times2$ squares within the $9\times9$ board, and there are $16$ different $2\...
D.J.'s user avatar
  • 304
9 votes
2 answers
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 ...
Oziter's user avatar
  • 349
9 votes
1 answer
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 ...
John Samples's user avatar
9 votes
1 answer
1k views

Coloring problem with limited number of each colors.

I’m investigating graph coloring problem. But I cannot find any solution about the problem with limited number of each colors. I mean, Suppose three colors(green, red, blue) and a graph, we start to ...
plhn's user avatar
  • 631
8 votes
3 answers
2k views

When chessboards meet dominoes

You probably have heard about the following brainteaser : Consider a $8\times 8$ chessboard. Remove two extreme squares (top-left and bottom-right e.g.). Can you fill the remaining chessboard with $...
vanna's user avatar
  • 1,524
8 votes
1 answer
1k views

Is Unit McGee rigid?

I figured out a unit distance embedding for the McGee graph. Bram Cohen asked me if it's rigid. I had a hard enough time figuring out this one embedding. If some points can move around, I might ...
Ed Pegg's user avatar
  • 21.3k
8 votes
5 answers
3k views

Is it possible to cover a $8 \times8$ board with $2 \times 1$ pieces?

We have a $8\times 8$ board, colored with two colors like a typical chessboard. Now, we remove two squares of different colour. Is it possible to cover the new board with two-color pieces (i.e. ...
user avatar

1
2 3 4 5
34