# Questions tagged [graph-colorings]

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

443
questions

**3**

votes

**1**answer

45 views

### For which sets of $(n, m, k)$ does there exist an edge-labelling (using $k$ labels) on $K_n$, such that every single-labelled subgraph is $K_m$?

Or, equivalently - for what sets of $(n, m, k)$ is it possible, for a group* of $n$ people, to arrange $k$ days of "meetings", such that every day the group is split into subgroups of $m$ people, and ...

**0**

votes

**0**answers

27 views

### Complexity of edge coloring of class 1 graphs

We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it ...

**-1**

votes

**1**answer

63 views

### Effect of collapsing two vertices of distance $2$

Motivating example. Consider the graph $G=(V,E)$ with $V = \{0,1,2,3\}$ and $E = \big\{\{i,i+1\}: i\in \{0,1,2\}\big\}$. We have $\chi(G) = 2$, but if we collapse $0$ and $3$, we get the complete ...

**3**

votes

**1**answer

65 views

### The effects of collapsing vs joining non-adjacent vertices on the chromatic number

For any set $X$, let $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$.
Is there a finite, simple, undirected, connected graph $G=(V,E)$ with the following properties?
There is $\{v, w\}\in [V]^2\...

**0**

votes

**0**answers

37 views

### Antimagic labelings to prove total coloring conjecture

An antimagic labeling of a simple graph with order $n$ and size $m$ is a surjective function from the set of edges to a set of labels (numbers) of size $m$ such that the sum of labels of the edges at ...

**1**

vote

**2**answers

87 views

### One part of a bipartite graph has max degree 3. Partition the other part to 3 ~equal subsets s.t. just a fraction of first part see all 3 subsets

Let $d \gg 1$. Let $G:=(U, V, E)$ be some bipartite graph such that deg$(u) \le d$ for all $u\in U$ and deg$(v) \le 3$ for all $v \in V$.
Now, is it possible to color vertices in $U$ with 3 colors ...

**22**

votes

**1**answer

424 views

### Doubly periodic 4 color theorem?

Let $G$ be a graph embedded (without crossings) on a torus $T$. It's fairly well known that this implies the chromatic number of $G$ is at most 7. If I lift $G$ to the universal cover of $T$, we get a ...

**5**

votes

**2**answers

100 views

### Is the acyclic chromatic number bounded in terms of the book thickness?

ISGCI says that the chromatic number of a graph is upper bounded in terms of the book thickness.
https://www.graphclasses.org/classes/par_32.html
This can be improved by saying that the book ...

**10**

votes

**1**answer

153 views

### Kneser subgraph with high chromatic number

For positive integers $n\geq 2k$, it is known that the chromatic number of the Kneser graph $K_{n,k}$ is $n-2k+2$. Moreover, the Schrijver graph $S_{n,k}$ (definition in the same link), which is a ...

**0**

votes

**0**answers

69 views

### Can you color a planar graph given a coloring of its triangulation?

Several proofs of the four color theorem (or failed attempts) start with something like "We need only consider triangulations, because every simple planar graph is contained in a triangulation".
On ...

**7**

votes

**1**answer

987 views

### Could the 4-color theorem be proven by contracting snarks?

Suppose someone came up with an algorithm that could take any snark and perform edge contraction to result in the Peterson graph. If an inspection of the algorithm reveals that it works as claimed, ...

**1**

vote

**0**answers

43 views

### Graph coloring to minimize maximum number of colors along paths

Given a graph $G$ and a pair of source-destination nodes $s$ and $t$. Each node in $G$ is to be colored. Let $C_i$ denote the available color set for node $i$. Under a coloring scheme $A$, for any $s-...

**1**

vote

**0**answers

41 views

### Upperbound on Shannon capacity of graph and strong product of graph

Given a Graph $G = (V=[n],E)$, if a symmetric matrix $B$ fits $G$, it has non-zero diagonal elements and 0 on off-diagonal entries if $\{i,j\}$ are non-edge in $G$.
Let \begin{equation}
R(G) = \min ...

**1**

vote

**1**answer

138 views

### A converse of the Erdős-De Bruijn Theorem?

For the chromatic number $\chi(G)$ of a simple, undirected graph, there is a "compactness" theorem by Erdős and De Bruijn stating that if an infinite graph $G$ has finite chromatic number, then there ...

**1**

vote

**0**answers

163 views

### Minimum vertex cover and linear programming

Suppose we have a graph G. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $v_{i}...

**0**

votes

**1**answer

32 views

### Starting point of roundtrip coloring in connected graphs

This is a subquestion for an older question about a certain kind of greedy coloring.
Let $G = (V,E)$ be a finite, connected, simple, undirected graph. By a roundtrip of $G$ we mean a map $r:\{0,\...

**2**

votes

**1**answer

88 views

### “Roundtrip”-chromatic number of (connected) graphs

Let $G = (V,E)$ be a finite, connected, simple, undirected graph. By a roundtrip of $G$ we mean a map $r:\{0,\ldots,n\} \to V$ for some $n\in\mathbb{N}$ with the following properties:
$r$ is ...

**2**

votes

**1**answer

75 views

### A problem about the connectivity of vertices that must have the same color for any proper minimal coloring of a graph

I did not get an answer when asking for help with this question in Math Stack Exchange (here). Anyway, I believe that this forum is more suitable for it.
I'm trying to solve a problem about ...

**0**

votes

**0**answers

118 views

### What is the number of connected graphs with $n$ vertices of max. degree up to $D$? Leaving $F(x) = x + x^2 + 2x^3 + 6x^4 + 21x^5 + 112x^6 + …$

It is known that F(x) is the generating function of the counting sequence of connected simple graphs with N vertices is given by:
$F(x) = x + x^2 + 2x^3 + 6x^4 + 21x^5 + 112x^6 + 853x^7...$
where ...

**2**

votes

**0**answers

41 views

### Lower bound for the chromatic number in terms of minimum feedback vertex set

Let $MFVS(G)$ denote the size of minimum feedback vertex set of $G$.
We believe we proved $\chi(G) \ge (|G| - MFVS(\overline{G}))/2$
and this bound is sharp.
Is this known or trivial result?
This ...

**1**

vote

**0**answers

47 views

### Partitionability and colorability of hypergraphs

Motivation. If $\kappa\neq\emptyset$ is a cardinal, then a simple, undirected graph $G=(V,E)$ is $\kappa$-colorable if and only if there is a partition of $V$ into at most $\kappa$ blocks such that ...

**0**

votes

**0**answers

29 views

### Tutte 1-factor theorem to prove total chromatic number of complete multipartite graphs

Consider a complete multipartite graph on $n$ vertices having maximum degree $\Delta$. Then, it is known that the total chromatic number of the graph is $\le\Delta+2$. The proof uses the fact that a ...

**1**

vote

**0**answers

87 views

### Relation between the number of spanning trees and the chromatic number of a graph

The number of spanning trees $\tau(G)$ of a simple graph $G$ is seen to satisfy the deletion-contraction recurrence:
$$\tau(G)=\tau(G-e)+\tau(G.e),$$
where $e$ is an edge of the graph $G$ and $G-e$ ...

**2**

votes

**2**answers

112 views

### Generalization of independence complex of graphs

Let $G$ be an undirected graph with no multiple edges or loops. Recall that the independece system $\mathcal{I}(G)$ consists of all those subsets $A$ of the vertex set such that the induced subgraph $...

**1**

vote

**1**answer

87 views

### Cliques in overlap graphs for words

Let $\Sigma$ be a finite alphabet, and consider the free monoid $\Sigma^*$. Given $w, w' \in \Sigma^*$ we say that $w$ overlaps $w'$ if there exist non-empty words $u, v, u'$ such that $w = uv$ and $w'...

**9**

votes

**1**answer

207 views

### When does a graph have a circular orientation? Or equivalently can anyone help me characterize this particular class of $3$-colorable perfect graphs?

Call an oriented digraph $D=(V,A)$ circular when for all $\small x,y,z\in V$ if $(x,y)\in A$ and $(y,z)\in A$ then $(z,x)\in A$ or equivalently if $D$ is any oriented digraph whose arc set is a ...

**1**

vote

**1**answer

58 views

### A different version of list coloring

Consider a non-regular bipartite graph $G$ . We consider list edge coloring the edges of the graph by giving lists of cardinality $max(deg(v_i),deg(v_j))+2$ for each edge $e=v_iv_j$ where $deg(v_i)$ ...

**2**

votes

**0**answers

48 views

### Analog of Reed's conjecture for hypergraph

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 number, $\Delta$ is the maximum degree, and ...

**5**

votes

**0**answers

161 views

### Cardinals realizable by the chromatic number of a regular hypergraph

For any set $X$ and cardinal $\kappa$, we denote by $[X]^\kappa$ the collection of subsets of $X$ having cardinality $\kappa$.
If $H=(V,E)$ is a hypergraph, and $\kappa$ is a cardinal, we say that a ...

**1**

vote

**0**answers

65 views

### Total Coloring of a graph with $\Delta\ge\frac{n}{2}$

Consider an even vertex transitive graph $G$, which is not complete, with order $n$ and degree $k$ greater than or equal to half the order. By Hajnal-Szemeredi theorem, we could partition the ...

**3**

votes

**1**answer

86 views

### What number of colorings can guarantee that for every k-element subset there exists a coloring assigns different colors for elements from this subset?

Let $M(n, k)$ be a minimal number $m$ such that there exists set $C$ ($|C|=m$) of colorings of n-element set $[n]$ with $k$ colors such that for every $k$-element subset $K$ of $[n]$ there exists ...

**3**

votes

**1**answer

63 views

### Minimal degree in a critical graph

We say that a finite, simple, undirected graph $G=(V,E)$ is $k$-critical for $k\in\mathbb{N}$ if $\chi(G)=k$ and $\chi(G\setminus \{v\}) = k-1$ for all $v\in V(G)$. Let $\delta(G)$ denote the minimum ...

**0**

votes

**0**answers

57 views

### The order of minor in the total graph of a graph

Does the total graph of a regular finite graph with maximum degree $\Delta$ have a $K_{\Delta+2}$ minor?
I think no. It has a clique of order $\Delta+1$. But, I dont think that deleting a few edges ...

**0**

votes

**0**answers

56 views

### Minimal degree difference for $k$-critical graphs on $n$ vertices

For a finite, simple, undirected graph $G=(V,E)$ let $\delta(G)$ and $\Delta(G)$ denote the minimum and maximum degree of $G$, respectively.
Is there a constant $K\in\mathbb{N}$ with the following ...

**-1**

votes

**1**answer

77 views

### Tuza theorem to prove vizing theorem

The Tuza theorem states that every graph with no cycle congruent to 1 mod $k$ is $k$ colorable. Now, the line graph of any simple graph of maximum degree $d$ is seen to posess the property that it has ...

**3**

votes

**0**answers

96 views

### Lorentzian (=Minkowskian) Hadwiger-Nelson problem: is the chromatic number finite?

Background: Some years ago, I collected a number of thoughts and partial results (which, based on Soifer's Mathematical coloring book, I believed were new) on the Hadwiger-Nelson problem in a note ...

**4**

votes

**1**answer

89 views

### Complexity of graph 3 coloring and counting algorithm

3-coloring a graph $G$ is equivalent to partitioning the
vertices of $G$ in three independent sets.
The smallest independent set $A$ is at most $n/3$ where $n$
is the order of $G$.
We have $G \...

**1**

vote

**0**answers

75 views

### Relation between Betti Numbers and Chromatic Number of a simple graph

Is there a relation between the betti numbers of a graph considered as a simplicial complex and its chromatic number?
Typically the first Betti number is said to be the cyclomatic number of the graph....

**12**

votes

**0**answers

124 views

### Does there exist 2-planar graph with chromatic number 8 or 9 or 10

A 2-planar graph is a graph that can be drawn in the plane so that each edge is crossed at most twice. It is known that every 2-planar graph satisfies that $|E(G)|\le 5(|V(G)|-2)$. This implies that ...

**2**

votes

**1**answer

53 views

### A simple equality for book embedding of two graphs

A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is ...

**3**

votes

**1**answer

181 views

### Concentration of monochromatic edges in a graph

Let $G$ be a graph of order $n$ with $m$ edges. Color each vertices uniformly at random with $q$ colors. It is easy to see that expected number of monochromatic edges (edge whose end vertices are of ...

**1**

vote

**0**answers

42 views

### Coloration of an interval graph with constraints [closed]

Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...

**3**

votes

**1**answer

136 views

### Edge coloring graphs is in P?

It is known that there exist polynomial time algorithm to approximate the Lovasz number or the supremum of Shannon capacity of graphs.
By Vizing's theorem, the graph $G$ has only two chromatic ...

**2**

votes

**1**answer

89 views

### Perfect graphs condition could be weakened?

The perfect graphs are generally defined as those graphs whose every induced subgraph has its chromatic number equal to its clique number.
Now,are there some examples where the clique number of graph ...

**1**

vote

**0**answers

92 views

### Chromatic number of certain graphs with high maximum degree

Let $G$ be the graph of even order $n$ and size $\ge\frac{n^2}{4}$ which is a Cayley graph on a nilpotent group but not complete. Can the chromatic number of this graph be determined in polynomial ...

**3**

votes

**1**answer

236 views

### Combinatorial equation system with exponentially many equations in quadratic many variables

A certain question on graph theory (about the existance of graphs with a certain coloring inherited by perfect matchings) can be translated into the satisfiability problem of a certain set of ...

**4**

votes

**0**answers

81 views

### Dinitz Conjecture extension to rectangles

The Dinitz Conjecture, which was proved later in a more general form by Galvin, stated that given an $n\times n$ array, its elements could be filled exactly like a latin square, where the elements in ...

**2**

votes

**1**answer

186 views

### List coloring of tripartite graph [closed]

Let $G$ be a tripartite graph with partite sets $A,B,C$. The graphs $A\cup B$, $B\cup C$ and $C\cup A$ are each bipartite. Let the maximum degree of the graph be $\Delta$.
Now, we know that the ...

**0**

votes

**1**answer

75 views

### If the core of a graph is a forest, then it is Class 1

It is a standard result, due to Fournier, that if the core of a graph (the induced graph by the vertices having their degrees equal to maximum degree of the graph) is a forest (acyclic), then the ...

**4**

votes

**0**answers

28 views

### Edge orientation of finite triangle-free graphs

Given a finite simple graph without triangles, I am interested in conditions ensuring that there exists an orientation of the edges such that the following holds.
There exists no cycle $x_0,x_1,\dots,...