Questions tagged [colorings]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
64 views

$n^2$-Grid $3n$-Coloring Game: Can we color a n-square grid with 3n colors s. t. we can't select n colors to get an histogram with $\Theta(n^2)$ area?

The coloring game is a game played between Alice and Bob. There exists a grid of size $n \times n$, where $n$ is a strictly positive integer. Each cell of the grid can be colored with a color that ...
user avatar
2 votes
1 answer
97 views

Where can I find a picture of the complete 9-map on a triple torus that corresponds to Heffter’s table?

What I’m looking for is the analogue of Figure 5 in the paper by Saul Stahl, The Othe Map Coloring Theorem, Mathematics Magazine 1985, which is a complete 8-map $M_8$ on the double torus $S_2$ that ...
user avatar
5 votes
0 answers
266 views

What do the circuits of this matroid look like?

Given any hypergraph $H=(V,E)$ we call a family of sets $I\subseteq E$ "indifferent" iff there exists a map $\phi:I\to V$ such that: $\forall X\in I(\phi(X)\in X)$ and $\forall X,Y\in I(X\...
user avatar
  • 2,371
1 vote
1 answer
175 views

Maximum number of colors for an optimal tiling which guarantees infinite paths

This question is a more applicable version of the question I've asked in mathexchange recently: What is the maximum number of colors we can use to color $N^2$ square sub-tiles of $N×N$ square block ...
user avatar
  • 289
2 votes
0 answers
78 views

How many ways to cover a N×N chessboard with white and black boxes by some restrictions?

Suppose we have a N×N chessboard and the boxes ■, □. We should cover the chessboard with those boxes but there can not have the 2×2 square $\scriptstyle{\begin{array}{cc}\square&\square\\ \...
user avatar
3 votes
1 answer
99 views

What number of colorings can guarantee that for every k-element subset there exists a coloring assigns different colors for elements from this subset?

Let $M(n, k)$ be a minimal number $m$ such that there exists set $C$ ($|C|=m$) of colorings of n-element set $[n]$ with $k$ colors such that for every $k$-element subset $K$ of $[n]$ there exists ...
user avatar
  • 33
4 votes
2 answers
208 views

Can different knots have the same numbers of quandle colorings for all quandles?

Let $K_1$ and $K_2$ be two knots such that for all finite quandles $X$, the number of colorings of $K_1$ by $X$ is the same as the number of colorings of $K_2$ by $X$. Then my question is, must $K_1$ ...
user avatar
4 votes
0 answers
52 views

Bipartite graphs with alternating edge colorings

I would like to find all graphs or lattices which satisfy the following conditions: (1) Graph is bipartite with vertex types $A$ and $B$ ($A$-vertices only connected to $B$-vertices and vice-versa) (...
user avatar
2 votes
1 answer
279 views

Homogeneous van der Waerden

The Erdős Discrepancy Problem is whether in any two-coloring of the naturals for any $C$ there is a sequence $d, 2d, \ldots nd$ such that the difference of red and blue numbers in it is more than $C$. ...
user avatar
  • 17.3k