# Tagged Questions

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 ...
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 ...
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 ...
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 ...
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 ...
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.
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?
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)$.
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, ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 27, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9371161460876465, "perplexity_flag": "head"}