# Questions tagged [graph-colorings]

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

568 questions
Filter by
Sorted by
Tagged with
126 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),\ldots,(1,2,n),(1,n,2),\ldots,(1,4,2),(1,3,2)\}$. Note ...
79 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 ...
43 views

### Definition of graph canonization and good textbook reference

I am struggling a bit with finding a good and generally accepted definition of graph canonization and canonical forms as well as a good textbook reference. From what I understand, a canonical form is ...
1 vote
61 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 ...
1 vote
62 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$...
167 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 ...
2k 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 ...
92 views

### List coloring as a homomorphism

A proper coloring of the vertices of a graph $G$ is seen as a homomorphism from the graph vertices to the complete graph on the number of vertices equal to the chromatic number of the graph. ...
224 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. ...
1 vote
69 views

### Chromatic number or independence number of the generalized Kneser Graph

For positive integers $n,k$ and $s$, where $0\le s<k$ and $k \le n$, we define the generalized Kneser graph $K(n,k,s)$ as follows: The vertices of $K(n,k,s)$ are the $k$-subsets of $[2n]$, i.e., we ...
83 views

23 views

### An edge has many colors on the edge colored graph

We know many properly colored problems, for example, properly colored hamilton path. If we admit that one edge has more than one colors, are there applications or similar research?
1 vote
54 views

### Hadwiger number and minimal degree (II)

This is a follow-up on an older question. Suppose $G$ is a finite simple graph and $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$. Let $\delta(G)$ is the minimal degree of ...
1 vote