The graph-colorings tag has no wiki summary.

**-2**

votes

**1**answer

52 views

### How does deletion-contraction affect chromatic number? Can it increase chromatic number? [on hold]

Question: In graph theory, contracting an edge or deleting an edge are basic operations in many topics such as graph minors or Wagner's theorem on planar graphs. And I'm interested in how these ...

**3**

votes

**1**answer

131 views

### Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...

**22**

votes

**1**answer

1k 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 ...

**49**

votes

**9**answers

6k 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 ...

**5**

votes

**1**answer

410 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, \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 ...

**14**

votes

**0**answers

182 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 ...

**19**

votes

**1**answer

896 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 ...

**25**

votes

**0**answers

581 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 = ...

**8**

votes

**1**answer

78 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 ...

**2**

votes

**1**answer

138 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 ...

**11**

votes

**0**answers

222 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$ ...

**3**

votes

**0**answers

107 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 ...

**2**

votes

**1**answer

103 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:
...

**2**

votes

**1**answer

92 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 ...

**1**

vote

**1**answer

49 views

### Graph of bounded continous functions with distance 1

Let $V = \{f:[0,1]\to \mathbb{R}: f \text{ is continuous}\}$ and consider the metric that is defined for $f,g\in V$ by $$d(f,g) = \max\{|f(t)-g(t)|: t\in [0,1]\}.$$
We set $E = \{\{f,g\}: f,g \in ...

**4**

votes

**1**answer

145 views

### Hadwiger's conjecture for coloring number instead of chromatic number

For any graph $G=(V,E)$, the coloring number $\text{Col}(G)$ is defined to be the smallest cardinal $\kappa$ such that there is a well-ordering $\leq$ on $V$ such that for every vertex $v\in V$ we ...

**1**

vote

**1**answer

70 views

### Hadwiger-Nelson problem in higher dimensions

Given a positive integer $n\in \mathbb{N}$ we define the Hadwiger-Nelson graph $\text{HN}_n$ by
$V(\text{HN}_n) = \mathbb{R}^n$;
$E(\text{HN}_n) = \{\{v_1, v_2\}: v_1, v_2 \in \mathbb{R}^n \text{ ...

**6**

votes

**1**answer

232 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 ...

**31**

votes

**9**answers

3k 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 and strengthenings of the four color theorem ...

**2**

votes

**1**answer

91 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$ ...

**10**

votes

**2**answers

422 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 ...

**6**

votes

**2**answers

397 views

### Minimal graphs of prescribed girth and chromatic number

The well known result of Erdős, states that
Given integers $g > 2$ and $k > 1$ there exist a graph $G$ with $\chi(G) \geq k$ and girth at least $g.$
What I am wondering is
When can we ...

**0**

votes

**0**answers

155 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 ...

**4**

votes

**1**answer

208 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 ...

**2**

votes

**1**answer

116 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?

**6**

votes

**0**answers

139 views

### Does the weak Hadwiger conjecture imply the Hadwiger conjecture?

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$.
...

**12**

votes

**1**answer

295 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 ...

**1**

vote

**0**answers

42 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$ ...

**6**

votes

**0**answers

127 views

### What is known about the chromatic number for minimum-distance graphs in higher dimensions?

For a set of points in $\mathbb{R}^d$ with minimum distance $a$, the minimum-distance graph connect two points iff they are at distance $a$. We can also view it as the tangency graph for a set of ...

**0**

votes

**2**answers

111 views

### Coloring of a normal map

can the following proposition be proved? If so please suggest a method. Can Kempe’s Argument be used for proof ?
Proposition: A normal map has a colouring of countries by 4 colours iff the edges of ...

**8**

votes

**1**answer

351 views

### Coloring of the plane

I would like to know the minimum number k such that the plane R^2 can be coloured with k colors such that no colour contain all the possible distances. In other words, a colouring such that each color ...

**1**

vote

**2**answers

62 views

### Coloring maximal independent sets with 1 color

Let $G$ be a graph and $M\subseteq V(G)$ be a maximal independent set. Is there a coloring $c:V(G)\to\chi(G)$ such that $c$ is constant on $M$?
(The answer is positive for graphs with infinite ...

**1**

vote

**2**answers

97 views

### Regular graphs with strongly regular edge colorings

Given a positive integer $c>1$, for what parameters $(v,k,\lambda,\mu)$ does there exist a $c k$ regular graph on $v$ vertices that can be given an edge coloring with $c$ colors, such that the ...

**0**

votes

**1**answer

196 views

### Coin graph is 4-colorable

How can we prove that a coin graph is 4-colorable???Also, can we find any example of an non-3-colorable coin graph.

**2**

votes

**1**answer

220 views

### On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections

Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements.
We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we ...

**3**

votes

**1**answer

82 views

### Coloring graph such that the coloring classes are not maximal independent sets

Let $G$ be a (finite or infinite) simple graph. We let $\mathrm{Ind}(G)$ be the collection of independent sets. For any cardinal $\kappa$ and coloring map $\chi: G\to \kappa$ we have ...

**1**

vote

**0**answers

195 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 ...

**6**

votes

**2**answers

292 views

### Matching number and chromatic number

If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$).
For odd integers $n$ we have $n=\chi(K_n) = ...

**2**

votes

**0**answers

205 views

### Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate
polynomial which counts the number of colorings of $G$
with $x$ colors for natural $x$.
Graph is not $k$ colorable iff $P(G,k)=0$.
The ...

**0**

votes

**0**answers

76 views

### asymptotic notation with graph colouring

This is my first ever post so I hope this is an appropriate question.
Basically I am looking at the paper here: http://homepages.math.uic.edu/~mubayi/papers/biclique.pdf
Namely theorem 5.
Now, feel ...

**34**

votes

**6**answers

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 ...

**7**

votes

**2**answers

227 views

### Conjecture: for perfect graphs the fractional chromatic index rounded up equals the chromatic index

Let $\chi'_f(G)$ be the fractional chromatic index.
Based on limited experiments (up to 8 vertices and few larger graphs),
I suspect:
Conjecture For perfect graphs $\lceil \chi'_f(G) \rceil = ...

**8**

votes

**1**answer

357 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 ...

**7**

votes

**2**answers

150 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 ...

**0**

votes

**0**answers

31 views

### number of bipolar orientations to acyclic ones

Given a $k$-regular graph $G$, is there an upper bound on the number of bipolar orientations that $G$ has?
I am trying to show that the number of bipolar orientations is much much lower than the ...

**4**

votes

**2**answers

170 views

### Is There a Graph that is Ramsey for $P_{2n}$ but is $C_{2n+1}-$free

Write $F\to G$ to mean that for every two coloring of the edges of $F$, there exists a monochromatic copy of $G$. Nesetril and Rodl proved that for a graph $G$, there exists a graph $F\to G$ with ...

**3**

votes

**1**answer

60 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 ...

**3**

votes

**0**answers

97 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$. ...

**10**

votes

**2**answers

184 views

### Big Mono-Chromatic Subgraphs of Vertex 2-Colourings

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 ...

**10**

votes

**9**answers

2k 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 ...