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
62 votes
19 answers
12k views

Generalizations of the four-color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors. The purpose of this question is to collect generalizations, variations, and strengthenings of the four ...
54 votes
10 answers
8k views

The "sensitivity" of 2-colorings of the d-dimensional integer lattice

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate). Let $C$ be a two-...
Scott Aaronson's user avatar
51 votes
0 answers
2k views

Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?

A very specific case of Reed's Conjecture Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic ...
Andrew D. King's user avatar
50 votes
15 answers
11k views

Strengthening the induction hypothesis

Suppose you are trying to prove result $X$ by induction and are getting nowhere fast. One nice trick is to try to prove a stronger result $X'$ (that you don't really care about) by induction. This ...
48 votes
5 answers
7k views

Algebraic proof of 4-colour theorem?

4-colour Theorem. Every planar graph is 4-colourable. This theorem of course has a well-known history. It was first proven by Appel and Haken in 1976, but their proof was met with skepticism because ...
Tony Huynh's user avatar
  • 31.5k
47 votes
7 answers
5k views

Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
Joel David Hamkins's user avatar
41 votes
4 answers
5k views

Why is "P vs. NP" necessarily relevant?

I want to start out by giving two examples: 1) Graham's problem is to decide whether a given edge-coloring (with two colors) of the complete graph on vertices $\lbrace-1,+1\rbrace^n$ contains a ...
Andreas Thom's user avatar
  • 25.3k
36 votes
0 answers
1k views

3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$. Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = (\alpha,...
Igor Pak's user avatar
  • 16.3k
34 votes
1 answer
3k 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,143
33 votes
3 answers
2k views

chromatic number of the hyperbolic plane

A notorious problem in combinatorics is the following: If we color $\mathbb{R}^2$ so that no pair of points at unit distance get the same color, what is the fewest number of colors required? This ...
Matthew Kahle's user avatar
32 votes
0 answers
3k views

Vertex coloring inherited from perfect matchings (motivated by quantum physics)

Added (19.01.2021): Dustin Mixon wrote a blog post about the question where he reformulated and generalized the question. Added (25.12.2020): I made a youtube video to explain the question in detail. ...
Mario Krenn's user avatar
31 votes
3 answers
2k views

Has there been a computer search for a 5-chromatic unit distance graph?

The existence of a 4-chromatic unit distance graph (e.g., the Moser spindle) establishes a lower bound of 4 for the chromatic number of the plane (see the Nelson-Hadwiger problem). Obviously, it ...
Juho's user avatar
  • 717
27 votes
1 answer
2k views

Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946

I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph ...
user19906's user avatar
  • 419
25 votes
1 answer
2k views

A Question on 1, 2 ,3 Conjecture

The 1, 2, 3 conjecture is well-known: If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the ...
Rahman. M's user avatar
  • 2,341
24 votes
2 answers
2k views

Can one measure the infeasibility of four color proofs?

Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...
Colin McLarty's user avatar
24 votes
1 answer
565 views

Doubly periodic 4 color theorem?

Let $G$ be a graph embedded (without crossings) on a torus $T$. It's fairly well known that this implies the chromatic number of $G$ is at most 7. If I lift $G$ to the universal cover of $T$, we get a ...
Nate's user avatar
  • 1,992
24 votes
0 answers
744 views

How much of the plane is 4-colorable?

In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...
Dustin G. Mixon's user avatar
21 votes
8 answers
8k views

Why is edge-coloring less interesting than vertex-coloring?

I was wondering why there is (apparently) much more research directed towards vertex-coloring than edge-coloring? Prima facie, it seems that edge-coloring is just as "natural" a thing to investigate. ...
21 votes
1 answer
1k views

Smallest known counterexamples to Hedetniemi’s conjecture

In 2019, Shitov has shown a counterexample (Ann. Math, 190(2) (2019) pp. 663-667) to Hedetniemi’s conjecture, $$\chi(G \times H)=\min(\chi(G),\chi(H))$$ where $\chi(G)$ is the chromatic number of the ...
Mario Krenn's user avatar
21 votes
2 answers
1k views

The chromatic number of the union of two graphs

Let $G_n$ be the graph on the set of all binary strings of length $n$ with two strings adjacent whenever they are Hamming distance $2$ away from each other, or one of them lies below another one; thus,...
Seva's user avatar
  • 22.8k
21 votes
0 answers
572 views

Coloring a Ferrers diagram

I've shopped the problem below around a bit and it seems like it might be known, or not that hard to resolve, but so far I've come up empty-handed. Say that a coloring of the dots of a Ferrers ...
Timothy Chow's user avatar
  • 78.1k
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
19 votes
0 answers
606 views

Simpler proofs of certain Ramsey numbers

The reason for the gorgeous simplicity of the classic proofs of $R(3,3)$, $R(4,4)$, $R(3,4)$ and $R(3,5)$ is that essentially all you need is the trivial bound and a picture. But for bigger Ramsey ...
Myshkin's user avatar
  • 17.4k
18 votes
3 answers
2k views

Does there exist a graph with maximum degree 8, chromatic number 8, clique number 6?

Question. Does there exist a graph $G$ with $(\Delta(G),\chi(G),\omega(G))=(8,8,6)$? Remarks. Here, 'graph'='undirected simple graph'='irreflexive symmetric relation on a set' any number of ...
Peter Heinig's user avatar
  • 6,001
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
17 votes
6 answers
10k views

Lower bounds for chromatic number of a graph

I am trying to find a good lower bound for chromatic number of one family of graphs. I'm curious what are the known lower bounds for chromatic number. There are two obvious: $\chi(G) \geq \omega(G)$ ...
ilyaraz's user avatar
  • 1,771
17 votes
3 answers
455 views

Graph that minimizes the number of b/w colorings where white vertices have an odd number of black

motivated from a physical context, we are currently interested in the following graph coloring problem: Given a connected graph $G_n$ with $n$ vertices, how many colorings exist such that all white ...
Herimon's user avatar
  • 323
17 votes
1 answer
426 views

"Good" edge-colorings

Let $n >1$ be an integer, and suppose $G = (V,E)$ is a simple undirected graph with $V = \{1,\ldots,n\}$. For $v\in V$ set $N(v) = \{w\in V: \{v,w\} \in E\}$. It is known by Vizing's theorem that ...
Dominic van der Zypen's user avatar
16 votes
9 answers
3k views

What is the Tutte polynomial encoding?

Pretty much exactly what it says on the tin. Let G be a connected graph; then the Tutte polynomial T_G(x,y) carries a lot of information about G. However, it obviously doesn't encode everything about ...
Harrison Brown's user avatar
16 votes
3 answers
2k views

Are infinite planar graphs still 4-colorable?

Imagine you have a finite number of "sites" $S$ in the positive quadrant of the integer lattice $\mathbb{Z}^2$, and from each site $s \in S$, one connects $s$ to every lattice point to which it has a ...
Joseph O'Rourke's user avatar
16 votes
1 answer
518 views

Chromatic numbers of infinite abelian Cayley graphs

The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...
JSE's user avatar
  • 19.1k
15 votes
5 answers
2k views

Can one make Erdős's Ramsey lower bound explicit?

Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number $R(k)$. Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large ...
Randomblue's user avatar
  • 2,937
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
15 votes
1 answer
1k views

Making a non-monotone function monotone

Consider a function $f: \{0,1\}^n \rightarrow \{1..R\}$. This function can be interpreted as a coloring $Color(v)$ of vertices in a unit n-dimensional hypercube in $R$ colors. We say there is a ...
Grigory Yaroslavtsev's user avatar
14 votes
5 answers
1k 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
14 votes
2 answers
1k views

Is there easy proof for triangle-free two-coloring of planar graphs?

By merging two-two color classes, the Four Color Theorem implies that every planar graph can be two-colored such that each color class induces a triangle-free graph. Is there a simpler proof for this ...
domotorp's user avatar
  • 18.3k
14 votes
3 answers
995 views

Is there a matrix whose permanent counts 3-colorings?

Actually, I suppose that the answer is technically "yes," since computing the permanent is #P-complete, but that's not very satisfying. So here's what I mean: Kirchhoff's theorem says that if you ...
Harrison Brown's user avatar
14 votes
1 answer
1k views

Bipartite graphs arising from two $k$-partitions of a given graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \dots, V_n)$ and $(U_1, U_2, \dots, U_n)$ be two partitions of $V(G)$ corresponding to proper $n$-colorings of $G$. Consider the bipartite ...
hbm's user avatar
  • 1,034
13 votes
3 answers
4k views

Is there any fast implementation of four color theorem in Python?

I'm now using scipy.spatial.Voronoi to generate a Voronoi graph, as shown here: voronoi graph. I'd like to apply the four color theorem on it, so that no adjcent regions share the same color. I ...
ReZhacai's user avatar
  • 139
13 votes
6 answers
3k views

A decision problem in graph coloring

It'll be great to get a pointer or answer to the following question: What is the complexity of the following problem? Given an unweighted and undirected graph, can we have a proper (not necessarily ...
Muse's user avatar
  • 261
13 votes
2 answers
2k views

What is the smallest 4-chromatic graph of girth 5?

It is known that the smallest 4-chromatic graph of girth 4 is the Grötzsch graph (11 vertices). What happens for girth 5? The Brinkmann graph (21 vertices) has chromatic number 4, girth 5 and is 4-...
Florent Foucaud's user avatar
13 votes
1 answer
252 views

Graphs with a coloring that majorizes all other colorings

By a coloring of a graph $G = (V,E)$ I mean a map $\kappa:V\to\mathbb{N}$ such that $\kappa(u)\ne \kappa(v)$ whenever $u$ and $v$ are adjacent. (Sometimes this is called a proper coloring but I am ...
Timothy Chow's user avatar
  • 78.1k
13 votes
1 answer
473 views

The universal labeling of graph

The universal labeling of a graph $G$ is a labeling of the edge set in $G$ such that in every orientation $\ell$ of $G$ for every two adjacent vertices $v$ and $u$, the sum of incoming edges of $v$ ...
Ali Dehghan's user avatar
13 votes
0 answers
1k views

A new lower bound for the chromatic number of a graph?

Let $S_{+}(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph $G$. Let $S_{-}(G)$ denote the sum of the squares of the negative eigenvalues and $q$ the ...
Clive elphick's user avatar
12 votes
2 answers
727 views

Postnikov's approach to perfect matchings of graphs

Over a decade ago Alexander Postnikov developed his own way of looking at perfect matchings of bipartite plane graphs. As I recall, he starts with a 2-coloring of the square grid and creates a new ...
James Propp's user avatar
  • 19.4k
12 votes
1 answer
419 views

Coloring $K_n$ via edge-weight sums

This is a question inspired by and tangential to "A Question on 1, 2 ,3 Conjecture"—and certainly much easier! Suppose one assigns a random edge weight among $\{1,2,3,\ldots,k\}$ to each edge ...
Joseph O'Rourke's user avatar
12 votes
1 answer
837 views

Coloring the edges of a torus graph

Question:Consider the $2k \times 2k$ grid graph on a torus. Is it true that for every $2$-coloring of the edges, there is an antipodal pair of vertices connected by a path that changes colors at most $...
Daniel Soltész's user avatar
12 votes
0 answers
253 views

Computing the number of ways to delete vertices sequentially without disconnecting a graph

Given a finite connected graph on $n$ vertices, we are trying to count the number of ways to label the vertices $1$ to $n$ so that deleting them sequentially in that order never disconnects the graph. ...
Dylan Thurston's user avatar
12 votes
0 answers
206 views

Does there exist 2-planar graph with chromatic number 8 or 9 or 10

A 2-planar graph is a graph that can be drawn in the plane so that each edge is crossed at most twice. It is known that every 2-planar graph satisfies that $|E(G)|\le 5(|V(G)|-2)$. This implies that ...
Xin Zhang's user avatar
  • 1,130
12 votes
0 answers
448 views

Colouring a graph whose edge set is a special union of cliques

I am trying to show that a certain family of graphs can always be properly coloured with at most $6$ colours (where "properly coloured" means that each vertex gets a colour and no edge has both ends ...
Gordon Royle's user avatar
  • 12.3k

1
2 3 4 5
13