# Questions tagged [graph-colorings]

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

**-3**

votes

**1**answer

80 views

### Maximum chromatic number of a $k$-regular graph [on hold]

Let $c_k$ be the maximum chromatic number that a $k$-regular graph can have. What is $\lim\sup_{k\to\infty}\frac{c_k}{k}$?

**-1**

votes

**1**answer

65 views

### $2n$-regular graphs with maximal chromatic number

Let $n\geq 1$ be an integer. Suppose $m\geq 2n+1$ is an integer. We construct the graph $\mathbb{Z}_m = (\mathbb{Z}/m\mathbb{Z}, E_m)$ where $$E_m=\big\{\{x,y\}:x, y \in \mathbb{Z}/m\mathbb{Z} \text{ ...

**2**

votes

**0**answers

51 views

### Total Coloring Conjecture for Cayley Graphs

The total Coloring Conjecture(TCC) states that any total coloring of a simple graph $G(V,E)$ has its total chromatic number bounded as $\chi^{T}(G)\le \Delta+2$ where $\Delta $ is the maximal degree ...

**3**

votes

**1**answer

67 views

### Generalized digraph homomorphisms and graph cores

Given any digraphs $G$ and $H$ we say a surjection $f:V(G)\to V(H)$ reduces $G$ to $H$ if and only if it satisfies $(u,v)\in E(G)\iff (f(u),f(v))\in E(H)$. Where if there exists at least one ...

**1**

vote

**1**answer

98 views

### On a theorem of Chetwynd and Hilton in Graphs

Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...

**0**

votes

**1**answer

84 views

### Chromatic Polynomials of Circulant Graph With Two Parameters

I have been working with the chromatic polynomials of circulant graphs of prime order $p$ with two distinct parameters, i.e.
$P_{p,i,j}(x):= P(C_{p}(i,j),x)$ with $1 \leq i \neq j \leq \ n/2.$
In ...

**3**

votes

**1**answer

63 views

### Optimal Strategies for a “Blind” Graph Coloring Game

By the "blind" graph coloring game I denote the following problem, which is played by two players:
player A has $k<n$ colors at hand to color the $n$ vertices of a graph $G$, but that player has ...

**4**

votes

**1**answer

74 views

### Minimum number of vertices in a $k$-chromatic graph of odd girth $g$

The odd girth of a graph $G$ is defined as the minimum length of an odd cycle in $G$. Let $n_g(k)$ denote the minimum number of vertices in a $k$-chromatic graph of odd girth $g$. What are the known ...

**8**

votes

**0**answers

119 views

### Minimal number of colours in distinguishing colouring of biconnected graphs

A colouring of edges of a graph is distingushing if no non-identity automorphism of the graph preserves this colouring.
Problem. Is it true that each biconnected graph possesses a distinguishing ...

**5**

votes

**0**answers

67 views

### Extending colouring of graphs using small number of colours

Conjecture (Csóka-Lippner-Pikhurko). If $G$ is a graph with each vertex of degree $\le d$ with at most $d-1$ pendant edges properly coloured, then this pre-colouring can be extended to all edges of $G$...

**4**

votes

**1**answer

208 views

### Understanding proof about chromatic number

Consider an undirected graph $K(n,k,i)$, with the all $k$-element subsets of $\{1,\dots,n\}$ as vertices, and two vertices connected by an edge if their sets intersect in less than $i$ elements.
...

**-1**

votes

**1**answer

37 views

### pruning a special graph

You are given a very special graph. The vertices of the graph come in three
columns: left, center, and right. The edges connect vertices from the left to
vertices in the center, and from the center to ...

**8**

votes

**0**answers

349 views

### Colored weighted Graphs with only monochromatic perfect matchings

The following purely graph-theoretic question is motivated by quantum mechanics.
Definitions: A bi-colored weighted graph $G(V,E)$ is an undirected graph where every edge is colored, and has a ...

**3**

votes

**1**answer

74 views

### Maximal matchings in connected graphs

Let $n\in\mathbb{N}$ be a positive integer. Is there a connected graph $G$ such that $G$ cannot be coloured with less than $n$ colours, and every two maximal matchings have non-empty intersection?
(I ...

**2**

votes

**2**answers

102 views

### Graphs in which all maximal matchings intersect

Let $G=(V,E)$ be a simple, undirected graph. A matching is a set $M\subseteq E$ consisting of pairwise disjoint edges. We say $M$ is maximal if it is maximal amongst all matchings in $G$ with respect ...

**4**

votes

**0**answers

133 views

### Groups inducing edge-colorings on graphs. Is this concept known?

Are the following concepts known in graph/group theory, and if Yes, what are they called and where to read about them? Because I do not know better, I gave them placeholder names for now.
1. ...

**2**

votes

**0**answers

67 views

### Tutte polynomial from independent sets of a graph

Let $G$ be a connected graph with chromatic polynomial $X(G,q)$. Since $k$-proper coloring a graph is same as partitioning the vertex set $V$ into $k$ independent sets (a subset of the vertex set in ...

**5**

votes

**1**answer

330 views

### Countable version of Erdös-Lovasz-Faber conjecture

Let $X$ be an infinite set, and let $(A_n)_{n\in\omega}$ be a collection of subsets of $X$ with the following properties:
$|A_m\cap A_n| \leq 1$ for $m\neq n\in \omega$, and
$|A_n|=\aleph_0$ for all $...

**4**

votes

**1**answer

109 views

### Increasing the chromatic number by “folding” two vertices of distance 2

Is there a finite, connected, simple, undirected graph $G=(V,E)$ such that
$G$ is not complete, and
whenever two vertices of distance $2$ are identified ("folded"), then the chromatic number ...

**1**

vote

**1**answer

42 views

### Optimal Graph Splitting

Question:
Given a finite symmetric TSP instance with $2n$ sites, what is the complexity of and what are algorithms for determining two sets of sites $A$ and $B$, each containing $n$ elemenents so that ...

**0**

votes

**0**answers

14 views

### Name for Spanning Trees Containing all Edges of a Minimum Weight Perfect Matching

This question is motivated by the task of "uniformly" bicoloring the vertices of a symmetric TSP-instance graph with $2n$ vertices.
A simple heuristical requirement for such a bicoloring could be ...

**3**

votes

**0**answers

103 views

### Hadwiger number of Erdös-Faber-Lovasz graphs

For any set $X$, let $[X]^2 = \big\{\{a,b\}:a,b \in X, a\neq b\big\}$.
We call a finite, simple, undirected graph $G=(V,E)$ an $n$-Erdös-Faber-Lovasz (EFL-) graph if there are $n$ subsets $S_1,\...

**5**

votes

**1**answer

69 views

### Discrete Hadwiger–Nelson problem variant

The Hadwiger–Nelson problem asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color.
We could build the following ...

**15**

votes

**1**answer

277 views

### Chromatic numbers of infinite abelian Cayley graphs

The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...

**0**

votes

**0**answers

43 views

### Edge coloring, with a special condition

I have a problem I am working on that can be reduced to the following case of edge coloring with a special condition.
Let $G$ be a directed graph with infinite vertices that are colored with $m$ ...

**0**

votes

**0**answers

28 views

### Algorithms for Balanced Coloring of Complete Symmetric Graphs

Question:
Has this the following problem already been studied:
given a complete, weighted, finite symmetric Graph $G$ with $kn$ vertices, assign to each of the vertices one color from $k$...

**3**

votes

**0**answers

66 views

### chromatic number of plane using Cairo pentagonal tiling

Scale the Cairo pentagonal tiling so the short side is of length 1. Then it is easy to colour the tiling with 8 colours, two parallel ribbons of four colours each, to establish that the chromatic ...

**1**

vote

**3**answers

327 views

### how to get the coefficient of a special term in the expansion of the graph polynomial?

What is the coefficient $c$ of the term $x_1^2x_2^2x_3^2\cdots x_{12}^2$ in the expansion of the following multivariable polynomial:
$(x_1-x_2)(x_1-x_3)(x_1-x_4)(x_1-x_{10})(x_2-x_3)(x_2-x_5)(x_2-...

**8**

votes

**1**answer

383 views

### Graphs with only disjoint perfect matchings, with coloring

The following purely graph-theoretic question is motivated by quantum mechanics.
Definitions: A bi-colored graph $G$ is an undirected graph where every edge is colored. An edge can either be ...

**6**

votes

**0**answers

93 views

### What is the smallest number of vertices in a graph whose every orientation contains a directed straight path of length 3

For a graph $\Gamma$ and a digraph $\vec H$ we write $\Gamma\Rightarrow \vec H$ if any orientation of $\Gamma$ contains an isometric and isomorphic copy of the digraph $\vec H$. Since each graph ...

**3**

votes

**0**answers

108 views

### Constructing Graph V from De Grey´s Minimum Bound For the Chromatic Number of a Plane

Background information:
In section 4.2, paragraph 2 of De Grey´s recently published paper (De Grey's Paper pdf), he constructs a graph V, which is used to construct the graphs W, M, and eventually ...

**4**

votes

**1**answer

93 views

### Size of triangle free graph with chromatic number $n$

What's the largest constant $c >1$ such that all triangle free graphs with chromatic number $n$ has atleast $\Theta(c^n) $ vertices?

**2**

votes

**2**answers

260 views

### How to label a tree with minimum cost?

Let $T = (V, E)$ be a tree. Let $\Sigma$ be a finite set of labels. Given a label function $\ell : V \to \Sigma$, the cost of $\ell$ is given by
$$\mu(\ell) = \left| \{(u,v) \in E \mid \ell(u) \neq \...

**21**

votes

**0**answers

536 views

### How much of the plane is 4-colorable?

In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...

**4**

votes

**1**answer

141 views

### Does the existence of a unique chromatic (possibly transfinite) number for every (possibly non-finite) simple graph imply the axiom of choice?

Assuming the axiom of choice I can write for any cardinal number $\kappa$ and any simple graph $G$ that a function $f$ is a $\kappa\text{-coloring}$ of $G$ if and only if the cardinality of the image ...

**1**

vote

**1**answer

57 views

### Strong and weak chromatic number of infinite bounded hypergraphs

This is a follow-up of an older question.
Let $H = (V, E)$ be a hypergraph such that every member of $E$ has more than $1$ element. Let $\kappa$ be a cardinal. We say that $c: V\to \kappa$ is a weak ...

**1**

vote

**0**answers

83 views

### Does anybody know how to prove or disprove the following guess about edge coloring of Hypergraphs?

Definition. Suppose $H=(V,E)$ is a hypergraph. Call a hyperedge $e=\{v_1,v_2,\dotsc,v_k\}$ a $k$-star if in the 1-skeleton of $H$ there is a copy of $K^{1,k-1}$ whose union equals $e$. (Obviously in ...

**1**

vote

**1**answer

60 views

### Strong and weak chromatic number of infinite hypergraphs of finite rank

Let $H = (V, E)$ be a hypergraph such that every member of $E$ has more than $1$ element. Let $\kappa$ be a cardinal. We say that $c: V\to \kappa$ is a weak coloring if for all $e \in E$ the ...

**0**

votes

**2**answers

99 views

### coloring infinite vertex transitive graph without large cliques

Let $G$ be an infinite vertex-transitive graph (this means that for every $u,w \in V(G)$ there exists an automorphism $\tau$ of $G$ such that $\tau(u) = v$).
We assume that $G$ is undirected, and does ...

**0**

votes

**2**answers

292 views

### Non-isomorphic graphs with diameter two [closed]

Let $n>1$ be an integer and $[n] = \{1,\ldots,n\}$. What is an example of non-isomorphic simple, undirected graphs $G_i = ([n], E_i)$ for $i=1,2$ with the following properties?
both $G_1$ and $G_2$...

**2**

votes

**1**answer

40 views

### Is the difference sequence of the maximum size of $k$-colorable subgraph non-increasing?

Given a simple graph $G=(V,E)$, we use $A_k$ to denote the vertex set of a maximum $k$-colorable subgraph in $G$ when $k\ge 1$, and $A_0=0$.
Will the sequence $|A_1|-|A_0|,|A_2|-|A_1|,\cdots,|A_{\...

**1**

vote

**0**answers

104 views

### Continuous functions “sharing” a point

Let $(X,\tau)$ be a topological space. By $\text{End}(X)$ we denote the collection of all continuous functions $f:X\to X$. We say $f,g\in \text{End}(X)$ share a point if there is $x\in X$ such that $f(...

**3**

votes

**1**answer

215 views

### Smallest triangle-free graph with chromatic number 5

The Grötzsch graph is triangle-free and has chromatic number 4. At 11 vertices it is the (unique) smallest graph with these properties.
What is the smallest number of vertices needed for a triangle-...

**2**

votes

**1**answer

68 views

### Hadwiger critical graphs of arbitrarily high chromatic number

This is an update to an older question admitting a trivial example to answer it.
Suppose $G$ is a finite simple graph. Let $h(G)$ denote the Hadwiger number of $G$; that is, the maximum $n\in\mathbb{...

**1**

vote

**1**answer

80 views

### Sum-coloring a tournament

If $G=(V,E)$ is a loopless finite directed graph and $v\in V$, we set $\text{In}(v) = \{(w,v): w\in V \land (w,v) \in E\}$.
Let $T=(V,E)$ be a tournament such that for every $v\in V$ the set $\text{...

**1**

vote

**1**answer

154 views

### Some question about a new type of graphs

Let $G$ be a simple graph such that some of its vertices are like a fork. i.e. there is vertices $w,x,a,v$ such that edges $[v,w]$ and $[w,a]$ are incident in $w$ and edges $[w,a]$ and $[x,w]$ are ...

**4**

votes

**0**answers

193 views

### Two types of criticality

Suppose $G$ is a finite simple graph. Let $h(G)$ denote the Hadwiger number (synonym: connected pseudoachromatic number, cf. [Abrams-Berman 2014, p. 315]) of $G$; that is, the maximum $n\in\mathbb{N}$ ...

**2**

votes

**0**answers

106 views

### graph coloring conjecture

Motivation: if smallest planar graph $G=(v,e)$ exist with $\chi(G)$ = 5, then $\delta(G) > 4$ and $\omega(G)< 4$, $e = 3v - 6$ . It's well known no such graph available. Could it be generalized? ...

**1**

vote

**0**answers

78 views

### Partition of sets of monomials

Given a degree $d>0$ and $x_1,\dots,x_n$, consider the set $S$ of monomials
\begin{equation*}
x_1^{i_1} \cdots x_n^{i_n}
\end{equation*}
with $0\leq i_j\leq d$ for $1\leq j\leq n$ (the exponents ...

**-5**

votes

**1**answer

75 views

### Graphs where every vertex can be its own color class

Let $G=(V,E)$ be a finite, simple, undirected graph. We say $G$ has the singleton coloring class property (SCCP) if for all $v_0\in V$ there is a vertex coloring $c:V\to\{1,\ldots,\chi(G)\}$ such ...