Questions tagged [graph-colorings]

Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.

Filter by
Sorted by
Tagged with
-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 ...
Xin Zhang's user avatar
  • 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 ...
hedgehog0's user avatar
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 ...
CCC's user avatar
  • 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 ...
Dominic van der Zypen's user avatar
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\...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ${\...
Dominic van der Zypen's user avatar
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$-...
Zach Hunter's user avatar
  • 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 ...
Dominic van der Zypen's user avatar
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 ...
Kregnach's user avatar
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 ...
Isomorphism's user avatar
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:...
J.Doe's user avatar
  • 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 ...
Dominic van der Zypen's user avatar
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$. ...
fawadria's user avatar
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 ...
Zach Hunter's user avatar
  • 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?
Leo Marcus's user avatar
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-...
asd's user avatar
  • 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 ...
Kregnach's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Roland Bacher's user avatar
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. ...
Alma Arjuna's user avatar
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 ...
Roland Bacher's user avatar
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),\\...
vidyarthi's user avatar
  • 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 ...
P.Labarque's user avatar
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 ...
Lucas Blakeslee's user avatar
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 ...
Mark S's user avatar
  • 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 ...
Fedor Petrov's user avatar
  • 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 ...
GMB's user avatar
  • 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-...
TanG's user avatar
  • 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 ...
Fabius Wiesner's user avatar
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}...
Fabius Wiesner's user avatar
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.
Marina Drygala's user avatar
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 ...
James Propp's user avatar
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 ...
domotorp's user avatar
  • 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 ...
Math_Y's user avatar
  • 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 ...
Valentin Brimkov's user avatar
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)$ ...
Dominic van der Zypen's user avatar
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$ ...
Fabius Wiesner's user avatar
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 \...
Fabius Wiesner's user avatar
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 \{...
Tom Solberg's user avatar
  • 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 ...
Yaakov Baruch's user avatar
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\...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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) \...
Dominic van der Zypen's user avatar
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 ...
wandering_lambda's user avatar
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 ...
vidyarthi's user avatar
  • 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 ...
Felix Schröder's user avatar
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 ...
pierreciv's user avatar
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$...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar

1
2 3 4 5
13