# Tagged Questions

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

60 views

109 views

### A variant of Nelson-Hadwiger Problem on the chromatic number of the plane

The famous Nelson-Hadwiger problem asks about the chromatic number of the graph $G$, with the vertex set $V(G)={\mathbb R}^2$ where $a_1=(x_1,y_1), a_2=(x_2,y_2) \in V(G) \$ form an edge iff $a_1-a_2$...
144 views

### How to choose a random proper coloring

I am studying proper colorings of complete bipartite graphs and I'd like to be able to pick a random proper coloring and the compute some things about it. Recall that a proper coloring of a complete ...
178 views

### Hypercube edge-coloring problem

Question: Is there a pairing (a fixed point free involution) of the vertices of the $n$-dimensional cube graph, and a $2$-coloring of its edges such that the number of color changes needed to get from ...
140 views

### a question about Brooks' Theorem for $\Delta =4$

From Brooks' Theorem, we know that if a graph $G$ satisfies that $\Delta (G)=4$ and there is no $5$-clique in $G$, then $\chi (G)\leq 4$. And it is easy to find a counterexample to the following: ...
145 views

### Relationship of clique, independence, and chromatic numbers

For any graph $G=(V,E)$ let $\bar{G}$ be the complement graph. Is $$\text{inf}\big\{\frac{\omega(G)+\omega(\bar{G})}{\chi(G)} : G \text{ is a finite graph}\big\}$$ known? If not, what lower bounds are ...
73 views

345 views

### A variant to the Hadwiger-Nelson problem

Consider the following graph $G=(V,E)$ where $V=\mathbb{R}^2$ and $E = \{\{x,y\}: x,y \in \mathbb{R}^2 \text{ and } |x-y|\in \mathbb{Q}\}$. What is $\chi(G)$? (This is a variant of the Hadwiger-...
105 views

### When the vertex covering number is smaller than the chromatic number

For any graph $G=(V,E)$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$. As noted here, we have $\tau(G) \geq \chi(G) - 1$ for all finite graphs $G$. I'm interested in graphs $G$ ...
756 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-...
234 views

### Prove or disprove this upper bound on chromatic number

Let $G$ be a simple connected finite graph and let $v \ge 4$ be the number of vertices, $E$ the number of edges, $\chi(G)$ the chromatic number , $\omega(G)$ the clique number and $\Delta$ the ...
721 views

### Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$ such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...
164 views

### How to construct a graph with arbitrarily large girth and large chromatic number? [closed]

Erdos theorem says it is possible and it is not so easy. What is the general procedure to construct graphs like Grötzsch graph?
67 views

### Rate of convergence of graph-theoretic quantity to fractional graph-theoretic counterpart

Let $G^n$ denote the OR product of a graph with itself $n$ times, i.e. the graph which has an edge between distinct vertices $(v_1,v_2,\ldots,v_n)$ and $(u_1,u_2,\ldots,u_n)$ if there exists some $i$ ...
5k 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 ...
167 views

For any cardinal $\kappa$, let $K_\kappa$ denote the complete graph on $\kappa$. We consider the following statements: (H) If $G$ is a graph and $\chi(G) = \kappa$ then $K_\kappa$ is a minor of $G$. ...
360 views

356 views

### Kempe chain color swaps in a partially colored map

Crossposted from math.stackexchange.com: http://math.stackexchange.com/questions/904932/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using ...
393 views

393 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 ...
275 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$ ...
3k 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 ...
193 views

### Bounds on chromatic number of $k$-planar graphs

A $1$-planar graph can be drawn in the plane so that each arc is crossed at most once by another arc. A $k$-planar graph can be drawn so that each arc is crossed at most $k$ times. Planar graphs are ...
71 views

### Graph construction to double coloring & Hadwiger number

For any graph $G$ let $\eta(G)$ be the Hadwiger number of $G$. Is there for every graph $G$ a graph $2G$ such that -- $\chi(2G) = 2\chi(G)$, and -- $\eta(2G) = 2\eta(G)$? For each one of the above ...
132 views

### Independence Number of K4-free planar graphs

The independence ratio is defined as the size of the maximum independent set divided by $n$. By the 4-color theorem, every planar graph with $n$ vertices has independence ratio at least $1/4$. Clearly,...
I'm not a graph theorist, but the following quantity came up in my work and I'm curious if it has been studied. Given a connected finite graph $\Gamma = (V,E)$ define:  c(\Gamma) = \min_{f : V \...
Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$. Consider the bipartite ...