The graph-colorings tag has no wiki summary.

**5**

votes

**2**answers

222 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) = ...

**0**

votes

**0**answers

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

**2**

votes

**0**answers

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

**6**

votes

**2**answers

198 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

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

**6**

votes

**0**answers

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

**33**

votes

**6**answers

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

128 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

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

**2**

votes

**1**answer

54 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

70 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

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

**5**

votes

**1**answer

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

**13**

votes

**3**answers

644 views

### Are infinite planar graphs still 4-colorable?

Imagine you have a finite number of "sites" $S$ in the positive quadrant
of the integer lattice $\mathbb{Z}^2$,
and from each site $s \in S$, one connects $s$ to every lattice point to which it
has a ...

**3**

votes

**1**answer

61 views

### How to prove a certain connection between the list-chromatic number of a bipartite graph and a cardinal?

Let $G=(L,R,E)$ be a complete bipartite graph, such that $|L|=\aleph_0$ and $|R|=\kappa$. I'd like to show that if $\kappa<2^{\aleph_0}$ then the list-chromatic number of $G$ can't be more than ...

**2**

votes

**1**answer

181 views

### Coloring of subgraphs of G^n

Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , ...

**3**

votes

**0**answers

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

**6**

votes

**1**answer

230 views

### What is the status of this strong form of Hedetniemi's conjecture?

In this question, a graph is a finite, undirected graph without loops or multiple edges, and a colouring of a graph is a proper vertex colouring. The product $G \times H$ of graphs $G$ and $H$ is the ...

**10**

votes

**1**answer

315 views

### Coloring $K_n$ via edge-weight sums

This is a question inspired by
and tangential to "A Question on 1, 2 ,3 Conjecture"—and certainly
much easier!
Suppose one assigns a random edge weight among $\{1,2,3,\ldots,k\}$ to each
edge ...

**16**

votes

**1**answer

629 views

### A Question on 1, 2 ,3 Conjecture

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

**6**

votes

**1**answer

278 views

### coloring in lattice

This is a mathematical question raised from engineering and physics:
Is there some established mathematical approach in filling a physical lattice with some colored basis (black and white here)? For ...

**2**

votes

**1**answer

99 views

### Achieving the largest possible minimum spacing between vertices of the same color in an integer lattice

Consider an infinite integer lattice, or an infinite hexagonal lattice with unit length edges. Provided a set of $k$ possible vertex colors, is there a known largest possible minimum spacing that can ...

**4**

votes

**3**answers

196 views

### Crystal structure, lattice, Graph and coloring

I am working across mathematics, physics and engineering. And I am looking for whether there exists already formally established knowledge in the field.
Given a periodic graph (actually a physical ...

**1**

vote

**1**answer

218 views

### When does graph Laplacian have eigenvalue -1?

Consider an undirected graph $G$ with (symmetric) adjacency matrix $A \in \{0,1\}^{n \times n}$ and degree sequence $d = (d_i)$ where $d_i = \sum_{j} A_{ij}$. Assume that every node has degree at ...

**7**

votes

**0**answers

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

**20**

votes

**3**answers

1k views

### Can one measure the infeasibility of four color proofs?

Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...

**5**

votes

**1**answer

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

**5**

votes

**1**answer

191 views

### Probability that a random edge coloring of the complete graph is proper

This is a repost of this math.se question that I am posting here since it received no attention there.
What is the probability that a random edge coloring of $K_n$ with
$m \geq n$ colors ...

**4**

votes

**2**answers

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

**1**

vote

**0**answers

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

**5**

votes

**2**answers

243 views

### Fractional chromatic number, find reference to a particular alternate definition for

I'm searching for a reference to a particular alternate definition of the fractional chromatic number of graphs.
Let me review the most common definition and basic properties first.
Let $ G $ be ...

**1**

vote

**3**answers

213 views

### Strategic vertex labeling

We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0(all vertices with ...

**2**

votes

**1**answer

274 views

### bipartite graph coloring

Hi, I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is a bipartite graph G with the two vertex sets V1, V2. Each ...

**2**

votes

**0**answers

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

**1**

vote

**1**answer

180 views

### A yes no question concerning induced group

We are given a permutation group G acting on a finite set X. Finite set $\Omega$ contains all mappings $\omega$ from the set X to finite set K. We define mapping $\hat{g}$ on the set $\Omega$ in the ...

**6**

votes

**0**answers

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

**4**

votes

**1**answer

441 views

### Vector chromatic number and Lovasz theta

For $\alpha \ge 2$, an $\alpha$-vector coloring of a graph $X$ is an assignment of unit vectors to the vertices of $X$ such that vectors assigned to adjacent vertices have inner product less than or ...

**6**

votes

**1**answer

227 views

### coincidence between minimal triangulation numbers and chromatic numbers

A friend and I were reading up on the classification of compact surfaces when we realized that the minimal number of triangles in a triangulation of the sphere, torus, and projective plane are 4 ...

**8**

votes

**3**answers

408 views

### Edge-coloring of the complete graph without any rainbow paths

For a given $2k-1$ edge coloring of the complete graph $K_{2k}$,
say a Hamiltonian path $P$ is a rainbow path if every color appears exactly once in $P$.
My question is
"For each $2k (k \geq 2)$, is ...

**2**

votes

**2**answers

378 views

### Coloring a graph by Maximum Independent Set extraction

recursively extracting a MIS from an undirected simple graph $G$ does produce a minimal coloring for $G$ ?
I searched extensively the internet and found a paper [1] which answer partially to this ...

**2**

votes

**1**answer

201 views

### Isomorphism of connected, rigid, N-regular graphs with chromatic index N?

Background/Motivation
I'm working on algorithms for canonical labeling of a certain class of graphs (motivated by biology). The "difficult" instances of this problem can be reduced to graphs of the ...

**4**

votes

**1**answer

204 views

### 2-Coloring a planar hypergraph

Consider a hypergraph (of rank 3) $H = (V, E)$ (where the rank of $H$ is the maximum cardinality of a hyperedge). $H$ is said to be planar if we can construct a planar graph $G = (V, A)$, and a ...

**0**

votes

**0**answers

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

**0**

votes

**1**answer

164 views

### Hypergraph coloring

I am investigating whether the following hypergraph is $2$-colorable.
Let $0\le c < d < e$ be fixed natural numbers and consider a graph on $2e$ vertices, with the vertices labelled as ...

**1**

vote

**3**answers

215 views

### Chromatic number of the power set

Let $X$ be a non-empty set. Consider $\mathcal{P}(X)$, the power-set of $X$. We say that $a,b \in \mathcal{P}(X)$ form an edge if and only if their symmetric difference is a singleton, i.e. ...

**1**

vote

**1**answer

267 views

### Graph Theory Terminology Question

Given a (non-multi)graph $G$ let $N_G$ be the least number of nodes that must be colored (by a single color) such that every other node in $G$ shares an edge with at least one colored node. (I am only ...

**3**

votes

**1**answer

191 views

### Coloring tensor products of graphs

Let $ G,H $ are simple finite graphs and $A = G \times H$. Here $ G \times H $ is the tensor product (also called the direct or categorical product) of $ G $ and $ H $.
Let $G$ has smaller chromatic ...

**4**

votes

**1**answer

189 views

### maps with a large number of 4-colorings

I brought this up in January, but now know more and can be more precise.
I will have two questions.
How much of this is known?
If you don't know the answer to 1, then who does?
I invite all ...

**1**

vote

**1**answer

390 views

### Regular graph colorings

[Since I didn't get any feedback at MSE, I dare to post this question here, too.]
Call a coloring $C:V(G) \rightarrow \lbrace 1,\dots,n \rbrace$ of a graph $G$ regular when every vertex with color ...

**2**

votes

**1**answer

173 views

### A Ramsey-like lower bound?

Does there exist a graph $G$ which cannot be properly vertex-coloured with 3 colours (i.e. $G$ has chromatic number at least 4), such that for every graph $H$, if $H$ contains a triangle but there ...