# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
1 vote
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 ...
1 vote
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 ...
1k views

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$-...
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 ...
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 ...
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 ...
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:...
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 ...
1 vote
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$. ...
1 vote
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 ...
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?
1 vote
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-...
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 ...
1 vote
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 ...
1 vote
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 ...
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. ...
1 vote
### 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 ...