# Tagged Questions

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

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

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 = (\... 0answers 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 ... 0answers 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 ... 0answers 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$... 0answers 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 ... 0answers 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 ... 0answers 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 ... 0answers 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,\...
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$. ...
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 ...
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. ...
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 ...
89 views

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 ...
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: ...
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$ ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
34 views

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