Skip to main content

# Questions tagged [coloring]

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

178 questions
Filter by
Sorted by
Tagged with
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 ...
• 171
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 ...
• 111
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 ...
• 1,453
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?
7 votes
2 answers
4k views

### Construction of a triangle-free graph of chromatic number $1526$

I found this exercise in Bollobas: Modern Graph Theory "Construct a triangle-free graph of chromatic number 1526" It is added not to use results from the chapter about Ramsey Theory. Now my ...
• 875
4 votes
2 answers
3k views

### Coloring dodecahedron

I found some months ago that there are the Polya's enumeration theorem to compute number of colorings of dodecahedron. I got interested to find how to show by using only Burnside's lemma that there ...
• 127
5 votes
2 answers
7k views

### How to find chromatic number of the $n$-dimensional hypercube $Q_n$?

How to find chromatic number the $n$-dimensional hypercube $Q_n$? I know $\chi(Q_2)$=2 , $\chi(Q_3)$=2 , $\chi(Q_4)$=4
• 413
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 ...
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 ...
• 20.1k
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 ...
• 4,115
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 ...
• 429
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)$ ...
• 341
8 votes
3 answers
2k views

4 votes
3 answers
4k views

### Chromatic polynomial of a grid graph

I have the following graph with $nm$ vertices: ...
4 votes
2 answers
612 views

### Is this braced heptagon a rigid graph?

In Mathematica, GraphData[{"UnitDistance", {21, 2}}] Is this 42-edge graph rigid? It has chromatic number 4. If it was floppy, that might make it an interesting tool in high-chromatic ...
• 21.2k
4 votes
1 answer
774 views