Questions tagged [graph-colorings]
Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.
610
questions
-1
votes
0
answers
69
views
Is there is a constant $c$ such that toroidal graphs are minor-$c$-colorable?
A toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross.
A minor of graph G is a graph obtained from G by ...
- 1,040
3
votes
1
answer
178
views
Sum of squares of chromatic roots of a bipartite graph
Given a graph $G = (V, E)$, we can calculate its chromatic polynomial $P(G, k)$, and it has $n$ (complex) roots, also known as chromatic roots. It is a well-known fact that the sum of chromatic roots ...
- 33
1
vote
1
answer
79
views
Clique number of $k$-critical graphs
A graph $G$ is called a ${\it{k}}$-${\it{critical}}$ graph if $\chi(G)=k$ and for any proper subgraph $H$ of $G$ we have $\chi(H)<k$， where $\chi(G)$ denotes the chromatic number of $G$. The ...
- 31
1
vote
0
answers
59
views
Colorability classes of graphs
Let $G=(V,E)$ be a simple, undirected graph, finite or infinite, with $V \neq \emptyset$. We consider the chromatic number $\chi(G)$ as a cardinal. We say that colorings $c:V\to \chi(G)$ are proper ...
- 43.6k
15
votes
1
answer
1k
views
Parity and the Axiom of Choice
Motivation. The three-dimensional cube can be formalized by $\mathcal P(\{0,1,2\})$ where vertices $x,y\in\mathcal P(\{0,1,2\})$ are connected by an edge if and only if their symmetric difference $x\...
- 43.6k
2
votes
1
answer
79
views
Is the Hadwiger-Nelson graph restricted to $\mathbb{Q}\times\mathbb{Q}$ bipartite?
Consider the graph on $\mathbb{Q}\times\mathbb{Q}$ where two members of $\mathbb{Q}\times\mathbb{Q}$ form an edge if and only if their distance is $1$. Is that graph bipartite? If not, what is its ...
- 43.6k
0
votes
1
answer
98
views
Hadwiger number of the Hadwiger-Nelson graph on $\mathbb{R}^2$
If $G =(V,E)$ is a simple, undirected graph (finite or infinite), and $\kappa \neq \emptyset$ is a cardinal, we say that the complete graph $K_\kappa$ is a minor of $G$ if there is a collection ${\...
- 43.6k
2
votes
0
answers
59
views
Constants for diagonal hypergraph Ramsey Theorem
For integers $n,s$, we write $K_n^{(s)}$ to denote the complete $s$-uniform hypergraph on $n$ vertices.
Given integers $k,s,r$, let $R(K_k^{(s)};r)$ denote the smallest $N$, such that for every $r$-...
- 2,734
3
votes
1
answer
119
views
The sequence of the power chromatic numbers $(\chi(G^n))_{n\in\mathbb{N}}$
For any finite, simple, undirected graphs $G, H$ we denote by $G\times H$ their categorical product. For any graph $G$ we let $G^1 = G$ and for $n\geq 1$ we let $G^{n+1} = G \times G^n$.
It is easy to ...
- 43.6k
0
votes
3
answers
114
views
Even regular planar graphs without 2-cycles
Related to another question I asked, some questions came up, the most important is the following:
Are there any 4-regular planar graphs without 2-cycles + 3-cycles?
Could someone draw an example if ...
- 73
0
votes
0
answers
48
views
Perfect graphs are normal graph
Let $G$ be a graph. We call $G$ normal if it admits two partitions: $V(G)=\bigcup \mathcal{I}=\bigcup \mathcal{C}$ where $\mathcal{I}$ is a collection of independent sets and $\mathcal{C}$ is a ...
- 251
0
votes
0
answers
37
views
Is it always possible to create a minimum depth tree where tree nodes are unique and have a 'choice'?
This is a somewhat long question thus sincere apologies beforehand. In a tree a node is a simple point. Now instead of a node let us consider a set of 'choice nodes' that have the following properties:...
- 101
2
votes
1
answer
60
views
Possible chromatic numbers of a hypergraph on $\omega$ with a deck of edges
Let $\omega$ denote the first infinite ordinal (also known as the set of natural numbers). We call a set $E\subseteq {\cal P}(\omega)$ a deck if for all $n\in \omega$, the set $E$ contains exactly one ...
- 43.6k
1
vote
0
answers
68
views
Constructing orientations that increase (directed) distances between vertices in a maximum independent set
An orientation of a simple undirected graph $G=(V,E)$ is a directed graph $G' = (V,E')$ that is constructed by including either $(u,v) \in E'$ or $(v,u) \in E'$, but not both, for all $(u,v) \in E$.
...
- 73
1
vote
0
answers
58
views
Correct dependence for "Local Coloring"
In Alon-Spencer's book, Probabilistic Lens #8, it is proven that for each $k$, there exists $\epsilon = \epsilon(k)>0$ such that for all large $n$, there exists an $n$-vertex graph $G$ with ...
- 2,734
20
votes
2
answers
1k
views
Non-definability of graph 3-colorability in first-order logic
What is a proof that graph 3-colorability is not definable in first order logic? Where did it first appear?
- 309
1
vote
1
answer
155
views
Edge-colored flat graphs
Say that an undirected graph without loops or multiple edges is $n$-colored if its edges are labelled with numbers in $\{ 1, \ldots, n \}$ so that adjacent edges have different labels.
Theorem [Alon-...
- 11
8
votes
2
answers
545
views
Three-dimensional triangulations with fixed number of vertices
My question is the following:
Are there triangulations of $S^3$ which (a) are non-degenerate, (b)
have four vertices, and (c) have no edges of degree two?
A side question:
If one represents this ...
- 73
1
vote
1
answer
114
views
Is the chromatic number of hypergraphs downward continuous?
Let $H=(V,E)$ be a hypergraph. The chromatic number $\chi(H)$ is the smallest cardinal $\kappa \leq |V|$ such that there is a map $c:V\to \kappa$ such that for all $e\in E$ having more than one ...
- 43.6k
1
vote
1
answer
27
views
Hamiltonian edge colouring of complete graphs with even numbers of vertices
Edges of the complete graph on $2n$ vertices can be colored with $2n-1$ colors such that only edges of different colors intersect.
Can this always be done such that for every pair of different colors ...
- 16.3k
6
votes
0
answers
375
views
Example of graph with strange property
I've also posted this problem in Math Stack Exchange (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.
...
- 193
1
vote
0
answers
86
views
A variation of packing chromatic numbers for $\mathbb Z^d$
Subercaseaux and Heule showed in
https://arxiv.org/abs/2301.09757
(The Packing Chromatic Number of the Infinite Square Grid is 15)
that $n=15$ is the smallest positive integer for which there
is a map ...
- 16.3k
3
votes
1
answer
94
views
Edge coloring of a graph on alternating groups
Let $G$ be the Cayley graph on the alternating group $A_n\,n\ge4$ with generating set $$S=\begin{cases}\{(1,2,3),(1,3,2),\\(1,2,\ldots,n),(1,n,n-1,\ldots,2)\}, &n\ \text{odd}\\ \{(1,2,3),(1,3,2),\\...
- 1,831
0
votes
0
answers
55
views
4CT for infinite aperiodic planar graphs [duplicate]
Inspired by the recent Einstein 'Hat' tiling.
Is Appel & Haken's proof still applicable to an infinite aperiodic graph ? Such a graph with 1 region less still remains an infinite graph, right? How ...
- 25
9
votes
4
answers
983
views
How can one construct a four-coloring of a tiling of the plane with Smith, Myers, Kaplan, and Goodman-Strauss's aperiodic monotile?
This is motivated by the new paper of Smith, Myers, Kaplan, and Goodman-Strauss, wherein they define the existence of an aperiodic monotile. Clearly their tiling is not three-colorable, so we have ...
- 131
33
votes
1
answer
2k
views
Can we three-color a tiling of the plane with Smith, Meyers, Kaplan, and Goodman-Strauss's einstein?
The tiling world is a bit aflutter recently with the drop of Smith, Meyers, Kaplan, and Goodman-Strauss's paper showing an einstein - a simply-connected polygon - that must aperiodically tile the ...
- 2,123
5
votes
2
answers
254
views
Chromatic index of an acyclic digraph
Let $G=(V, E)$ be an acyclic digraph (DAG) with all in- and out-degrees at most $k$. Is it true that the edges of $G$ may be always colored properly in $2k$ colors?
In the discussion of this question ...
- 96.9k
0
votes
0
answers
41
views
Are $c$-edge-colored clique removal lemmas known when $c>2$?
The following is a rephrasing of the Induced Graph Removal Lemma by Alon, Fischer, Krivelevich, Szegedy:
For all $k>0$ and all $\epsilon > 0$, there is $\delta > 0$ such that the following ...
- 1,369
0
votes
0
answers
46
views
Maximum number of h-dimensional hyper-edges without forming any (h+1) complete subgraph
This is about graph theory.
Define an h-dimensional hyperedge as a set that contains h vertices.
A graph of (h+1) vertices is h-complete if any h combination (or any subset with size h) is an h-...
- 23
1
vote
0
answers
58
views
Lower bound for the minimum of the maximum frequency of an element - with restrictions
Consider a family $\mathcal{F}$ of non-empty sets, with
$n=|\mathcal{F}|$ sets, $q=\left|\cup\mathcal{F}\right|$ elements in the universe, and $q\le n/4$.
It is known that of the $\binom{n}{2}$ ways ...
- 610
1
vote
1
answer
70
views
Improving a lower bound for the minimum of the maximum frequency of an element in a family of sets
[Originally posted at math.stackexchange without answer]
Consider a family $\mathcal{F}$ of $n=|\mathcal{F}|$ sets, $\emptyset \not\in \mathcal{F}$ and an universe $U(\mathcal{F})$ of $q=|U(\mathcal{F}...
- 610
3
votes
1
answer
139
views
For every partition of $E(K_{n,n})$ into $n$ colour classes of size $n$, there is a vertex incident to at least $\sqrt{n}$ colours
Given a partition of the edges of $K_{n,n}$ into $n$ colours, where each colour appears exactly $n$ times, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.
8
votes
0
answers
270
views
Goldberg-Seymour conjecture
I am wondering whether the graph theory community regards the Goldberg-Seymour conjecture as settled. According to the Wikipedia entry on the Goldberg-Seymour conjecture, "In 2019, an alleged ...
- 19k
1
vote
0
answers
52
views
Chromatic number of 2-graph vs hypergraph of point-line incidences
Define the chromatic number $\chi(H)$ of a (hyper)graph $H$ as the smallest $k$ such that its vertices can be $k$-colored such that no (hyper)edge is monochromatic.
Given a finite set of points $P$ in ...
- 18.4k
0
votes
0
answers
86
views
How to find a specific clique cover set?
Let $G(\mathcal{V},\mathcal{E})$ be a graph with vertex set $\mathcal{V}$ and edge set $\mathcal{E}$. Also, non-negative weights $w_i$ are assigned to each vertex $i\in\{1,\ldots,n\}$. Suppose the ...
- 201
1
vote
0
answers
57
views
Complexity of EFL coloring of a set of lines
Let $M$ be a set of straight lines. Define an EFL coloring of $M$ with $k$ colors as a function $f : P(M) \rightarrow \{ 1,2,\dots,k \}$, such that if two intersection points $p_1, p_2$ belong to the ...
2
votes
1
answer
96
views
"Combined" chromatic number of $2$ graphs glued together with $2$ edges per vertex
If $X$ is any set, we let $[X]^2:=\big\{\{x,y\}:x\neq y\in X\big\}$. If $G=(V,E)$ is an undirected graph and $v\in V$, we define $N_G(v) = \{w\in V:\{v,w\}\in E\}$.
For $i =1,2$, let $G_i=(V_i,E_i)$ ...
- 43.6k
1
vote
1
answer
110
views
Graphs with $n$ vertices and $m$ edges and more probable property
Following to my previous question on the same topic, I would like to have some opinions whether the present refinement have some chances to work or is doomed to fail.
Given the positive integers $n$ ...
- 610
1
vote
2
answers
193
views
Do all graphs with $n$ vertices and $m$ edges have a special property?
Given the positive integers $n$ and $m$, consider the set of graphs $\mathcal{G} = \{G=(V,E): |V|=n \land |E|=m\}$.
For which values of $n$ and $m$ does the following requirement hold:
$\forall G \in \...
- 610
3
votes
0
answers
92
views
The matrix representation of an interval graph
It is well-known that many classes of graphs have matrix representations that can be written concisely. For example,
The set of all directed acyclic graphs consists of binary matrices $x_{ij} \in \{...
- 3,868
18
votes
2
answers
2k
views
Can the positive integers be colored so that elements of same color never add to a square?
Can one color the positive integers with finitely many colors, so that no two different numbers of the same color add to a square?
Some easy to prove remarks:
at least 4 colors are needed, since the ...
- 4,663
3
votes
1
answer
97
views
Property $\mathbf{B}$ for maximal linear set systems on $\omega$ with finite members
Let $X\neq\emptyset$ be a set. A family ${\cal S}\subseteq {\cal P}(X)$ has property $\mathbf{B}$ if there is $T\subseteq X$ such that for all $S\in{\cal S}$ we have $S\cap T\neq \emptyset$ and $S\not\...
- 43.6k
2
votes
1
answer
136
views
De Bruijn–Erdős theorem for hypergraphs
The De Bruijn–Erdős theorem states that when all finite subgraphs of a graph $G$ can be colored with $n$ colors, the same is true for the whole graph.
There is a natural notion of coloring for ...
- 43.6k
1
vote
2
answers
128
views
Do graphs with identical degree matrix have the same chromatic number?
If $G = (V, E)$ is a simple, undirected graph and $T \subseteq V$, let $$N(T) = \{v \in V: \{v, t\}\in E \text{ for some }t\in T\}.$$
Given $v\in V$ we let $N_0(v) = \{v\}$ and $N_{k+1}(v) = N_k(v) \...
- 43.6k
6
votes
2
answers
373
views
Coloring of a graph representing the power set
For a positive integer $n$, let $\mathcal{P}$ be the power set of $[n]$. Consider the graph $G$ with $\mathcal{P}$ as its vertex set, and, for $S_1,S_2 \in \mathcal{P}$, the edge $(S_1,S_2)$ exists ...
- 135
7
votes
2
answers
364
views
3-coloring the alternating group graph
Consider the alternating group graph, here defined as a Cayley graph on the alternating group $A_n$ using the generating set $\{(1,2,3),(1,2,4),\dotsc,(1,2,n),(1,n,2),\dotsc,(1,4,2),(1,3,2)\}$. Note ...
- 1,831
4
votes
1
answer
252
views
Construction of graphs of high girth and chromatic number
Are there any concrete constructions of graphs of both high girth and chromatic number?
Of course there is the seminal paper of Erdős which proves the existence of such graphs via the probabilistic ...
- 128
1
vote
1
answer
119
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 ...
- 11
1
vote
1
answer
72
views
Edge sets on $\omega$ maximal with respect to chromatic number
If $H=(V,E)$ is a hypergraph, and $\kappa \neq \emptyset$ is a cardinal, a map $c: V\to \kappa$ is said to be a coloring if the restriction $c|_e: e\to \kappa$ is non-constant whenever $e\in E$ and $e$...
- 43.6k
3
votes
0
answers
181
views
Conjecture on connected hypergraphs
A hypergraph $H=(V,E)$ with $V$ non-empty is said to be connected if for all $S\subseteq V$ with $\emptyset \neq S \neq V$ there is $e\in E$ such that $e$ intersects both $S$ and $V\setminus S$.
Given ...
- 43.6k