Tagged Questions

0
votes
0answers
106 views

(3n,n)-Turán graph [closed]

I'm working on a problem regarding (kn,n)-Turán graphs. The (2n,n)-Turán graph, also known as the cocktail party graph, has a closed formula for its number of spanning trees. I want to know if there ...
4
votes
4answers
140 views

Colouring a chessboard

How can I demonstrate that I can colour a $2n\times\binom{2n}{2}$ chessboard, with $n$ different colours, such that there aren't $4$ separate unit squares of the same colour, the centers of which are ...
2
votes
1answer
71 views

Coloring numbers from $1$ to $1000$

I mostly just need someone to explain to me this problem: Prove that it is possible to $2$-color the integers from $1$ to $1000$ so that no monochromatic arithmetic progression of length $17$ is ...
3
votes
1answer
48 views

example of a finite coloring without infinite monochromatic set closed under addition

I am studying some theorems on combinatorial set theory, especially Ramsey theorem and Hindman's theorem. I think I am going to ask a silly question, but I am too much involved in the subject to think ...
4
votes
1answer
94 views

Triangle free graphs with large chromatic number

I am trying to understand the proof of Theorem 2 given here. (Page 5) The theorem states that $\forall k\exists$ a triangle free graph $G$ with $\chi(G)>k$. The proof constructs such a $G$ as ...
0
votes
1answer
173 views

Planar graph with a chromatic number of 4 where all vertices have a degree of 4.

Is it possible to have a planar graph with a chromatic number of $4$ such that all vertices have degree $4$? Every time I try to make the degree condition to work on a graph, it loses its planarity.
2
votes
1answer
99 views

Can a planar graph without two triangles that share an edge have a chromatic number larger than 3?

Let G be a square with one diagonal. Are there any planar graphs without G as a subgraph that are not 3-colourable?
10
votes
1answer
84 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)$.
3
votes
1answer
63 views

Coloring points in a cycle

I have a question that relates to the Widom-Rowlinson model of statistical physics. Take a cycle on $n$ vertices. How many ways are there to color the $n$ vertices with the colors $\{\text{Red, ...
2
votes
0answers
65 views

Monochromatic degenerate triangles in a two-coloring of the plane

In a similar vein to a question I asked a few days ago: Do all two-colorings of $\mathbb{R}^2$ contain three points of the same color which form the vertices of a degenerate triangle of side-lengths ...
2
votes
0answers
96 views

Monochromatic triangles in a two-coloring of the plane

A problem posed to me by a friend: Show that any two-coloring of $\mathbb{R}^2$ that contains a monochromatic equilateral triangle of side-lengths 1 also contains monochromatic triangles of all side ...
0
votes
1answer
130 views

Edge colorings of complete graphs without tricolored triangles

Please prove the following theorem from Gallai : Theorem .In every coloring of a complete graph with three colors that avoiding rainbow triangle , at least one of the color classes must be ...
6
votes
2answers
392 views

Checkerboard-Coloring $\mathbb{Z}^2$

If every square of the unit square lattice in the plane is colored black or white according to a set of rules, is there a way to find the maximum asymptotic ratio $r_n$ of the number of black squares ...
4
votes
1answer
67 views

References for analogues of chromatic polynomials where colorings which differ only by permutation of colors are counted as the same

It's well-known that chromatic polynomials count colorings which differ by permutations of colors. What is known about their analogues which don't count such colorings as distinct?
1
vote
2answers
141 views

Coloring points on an n-gon

Given an $n$-sided polygon, how many ways can you color the vertices using $k$ colors so that no two adjacent vertices have the same color? (Inspired by 2011 AMC 12 A #16 – I'm able to do this for ...