**8**

votes

**1**answer

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

**35**

votes

**0**answers

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

**29**

votes

**0**answers

730 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 = (\...

**19**

votes

**0**answers

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

**16**

votes

**0**answers

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

**11**

votes

**0**answers

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

**11**

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

**8**

votes

**0**answers

135 views

### Edge-colorings of plane graphs: do you know references where the following questions are studied?

Let $G$ be a plane graph (or more generally, a graph embedded on a surface) with a proper edge-coloring of $G$ with $k$ colors $\{1,\ldots,k\}$. I am interested in studying the cyclic permutations of ...

**8**

votes

**0**answers

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

**7**

votes

**0**answers

249 views

### A maximum discrepancy hypergraph 2-colouring problem

This is sort of a hypergraph-ish question that I feel should be easy to prove or disprove but I can't see it right now.
The setup is as follows. We have a vertex set partitioned in to sets $V_1,\...

**6**

votes

**0**answers

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

**6**

votes

**0**answers

322 views

### Maximum fractional chromatic number of a 4-regular triangle-free graph (updated)

Let $G$ be a graph with maximum degree 4 and clique number 2. The fractional version of Reed's Conjecture tells us that $\chi_f(G) \leq 7/2$. But how high can $\chi_f(G)$ be?
The Chvátal graph has ...

**6**

votes

**0**answers

349 views

### What is this subclass of $k$-colorable graphs called?

The following property emerged naturally when I was playing with certain generalizations of Kneser graphs.
Let $k>0$ be a natural number. Consider a property $P_k$ of graphs defined as follows.
...

**5**

votes

**0**answers

74 views

### Chromatic numbers for coloring-constrained graphs

I am interested in any and all articles about chromatic numbers applying to constrained colorings of a graph. For example, if a graph must be (properly) colored so that there is a 2-color path ...

**4**

votes

**0**answers

89 views

### A color interpolation lemma

I need the following "color interpolation lemma". Actually I know a way to prove it, but I'm not very satisfied with that proof.
Lemma. Let $G=(V,E)$ be a (properly) colored graph with colors $1, \...

**4**

votes

**0**answers

76 views

### A relaxation of proper coloring

I am wondering if the following relaxation of proper coloring appears somewhere. I have tried some searching and have found a few relaxations of proper coloring, but none the coincides with what I ...

**4**

votes

**0**answers

69 views

### Existence of certain graph gadget related to coloring odd hole free graph

Wondering about the existence of graph gadget related to coloring
(or 3-coloring) odd hole free graphs.
Let $G$ be simple $k$-chromatic connected graph with two
vertices $u,v$.
Is it possible $G$ to ...

**4**

votes

**0**answers

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

**4**

votes

**0**answers

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

**3**

votes

**0**answers

67 views

### Is the chromatic number of the graph of the permutahedron known?

The permutahedron $\Pi_n$ is the polytope that is the convex hull of all permutations of the vector $(1,2,...,n)$. There are many results on its structure, but I couldn't find a result on the ...

**2**

votes

**0**answers

63 views

### Number of $(2n-1)$-edge-colorings of the complete graph $K_{2n}$

I just started reading about graph theory and have a question (which might be trivial). How many $(2n-1)$ edge colorings of $K_{2n}$ are there?
A vaguer question: can I write $K_{4n}= K_4 + K_4 +.......

**2**

votes

**0**answers

71 views

### Blossoms and Colorings

There is a striking analogy between finding maximum matchings in graphs and determining the chromatic number of graphs: both problems are fairly easy for bipartite graphs, but harder, resp. too hard ...

**2**

votes

**0**answers

59 views

### Planar triangulations for which all distinct 4-colorings consist of exactly 6 Kempe chains

Are there any internally 6-connected planar triangulations other than the icosahedron all of whose distinct 4-colorings consist of exactly 6 Kempe chains, one for each of the 6 color-pairs?
Addendum: ...

**2**

votes

**0**answers

52 views

### The numbers of edge colorings and partitions into vertex covers

Let $G = \langle X \cup Y, E\rangle$ be a $d$-regular bipartite graph such that $|U|=|V|=n$, and assume that $d$ divides $n$. Let $F(G)$ denote the number of proper edge colorings of $G$ using $d$ ...

**2**

votes

**0**answers

80 views

### Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

96 views

### Size of b-matching constructed from b maximal matchings

The Question: Let $G$ be a (simple) graph and let $b\in\mathbb{N}$. Suppose that we have $b$ disjoint edge-subsets $M_1,\ldots , M_b$ satisfying the following condition: The set $M_1$ is a maximal ...

**2**

votes

**0**answers

172 views

### Clique number of a $k$th power of a graph in terms of maximum degree?

Let $G$ be a graph of maximum degree $d$. Are there any known/easy bounds on the clique number of $G^k$, in terms of $d$ and $k$? I would like something at least epsilon better than the bound on the ...

**2**

votes

**0**answers

192 views

### Maximum number of 4-colorings of planar graphs (precise version)

This is a redo of my earlier question.
I'm trying again with more precision. I ignored one of the dicta in the "how to ask" page.
For a fixed $n$, what is known (references preferred) about the ...

**2**

votes

**0**answers

135 views

### finding set of tree decompositions to cover all pairs of vertices

I first asked this on cstheory.SE but got no reply.
Let $P(X_i=x)$ represent probability that randomly chosen proper $q$-coloring of an $L\times L$ square grid contains color $x$ at position $i$. How ...

**1**

vote

**0**answers

66 views

### A property of minimal prime ideals in rings with finite chromatic number

Let $R$ be a commutative ring with identity. There are so many ways to associate a graph to $R$. Consider this: take the elements of $R$ (All elements including zero) as vertices an two distinct ...

**1**

vote

**0**answers

114 views

### 2-edge colorable graph approximation

A 2 edge-colorable graph is a graph in which we can color the edges with two colors, in a way such that no edges of the same color share a vertex.
Given a graph G = (V,E) I want to find a 2 edge-...

**1**

vote

**0**answers

34 views

### Colorful Neighborhoods

Given:
$G:=\{V= \{v_1,\ ...\ v_n\},E\subset V\times V\}, n<\infty$, a symmetric complete, simple graph
$w:=\ \ E \ni e_{ij}\mapsto \mathbb{R}^+$, a weight function for the edges of $G$
$K:=\{c_1,\ ....

**1**

vote

**0**answers

39 views

### Stochastically coloring a graph in a local way

Suppose you are assigning values in $S$ (assume $|S|<\infty$) to nodes of a (directed) graph in a stochastic way. At the beginning, none of the node is assigned values. At the $i^{th}$ step, you (...

**1**

vote

**0**answers

65 views

### Proper edge colorings with no bi-colored 5-paths

Consider you want to properly edge color a graph such that it has no bi-colored cycle. Denote by $\alpha'(G)$ the least number of colors required to color the edges of $G$ in such a way.
It is well ...

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

146 views

### 3-edge-coloring of 3-regular multigraphs

Given that a 3-regular multigraph is 3-edge-colorable, is there an expression for how many 3-edge-colorings exist?
(For example, if a 2-regular multigraph is 2-edge-colorable, there are $2^k$ 2-edge-...

**0**

votes

**0**answers

25 views

### Permutation Invariant Color Class

$G$ is a $d$ regular graph, it has $n$ vertices.
$S_n$ acts on $n$ vertices of graph $G$.
Question: Does there exist a coloring algorithm for which color classes is invariant under all ...

**0**

votes

**0**answers

25 views

### Example/ Explanation of Weisfeiler-Lehman method

I am trying to read An Optimal Lower Bound on the Number of
Variables for Graph Identification. On page 3 (4th paragraph), it is written-
It might color vertices and edges implicitly by using $k$-...

**0**

votes

**0**answers

26 views

### Possible Number of Repetation of a Submatrix

Notation:
$H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...

**0**

votes

**0**answers

140 views

### Graph Coloring: Two adjacent vertices share same color

Consider, subgraphs $G_1, G_2,...... G_x$ of graph $G$. Each subgraph has $k$ vertices.
Now, Fix subgraph $G_1$ and consider another subgraph $G_k$ where $1 <k \le x$.
The edge set ...

**0**

votes

**0**answers

166 views

### SDP based heuristics for graph coloring

This is a question about semidefinite programming heuristics for graph vertex coloring based on the Lovasz theta number such as "Approximate Graph Coloring" by Karger, Motwani and Sudan or "A ...

**0**

votes

**0**answers

84 views

### A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where $\beta\...

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

219 views

### A copy of the Vizing's classic article about List Coloring.

Does anyone know where I get a copy of the Vizing's classic article about List Coloring?
"V. G. Vizing, Coloring the vertices of a graph in prescribed colors, Metody Diskret. Anal. v Teorii Kodov i ...