Questions tagged [graph-colorings]

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

Filter by
Sorted by
Tagged with
6 votes
1 answer
126 views

3-coloring the alternating group graph

Consider the alternating group graph, here defined as a Cayley graph on the alternating group $A_n$ using the generating set $\{(1,2,3),(1,2,4),\ldots,(1,2,n),(1,n,2),\ldots,(1,4,2),(1,3,2)\}$. Note ...
user avatar
  • 1,721
4 votes
1 answer
79 views

Construction of graphs of high girth and chromatic number

Are there any concrete constructions of graphs of both high girth and chromatic number? Of course there is the seminal paper of Erdős which proves the existence of such graphs via the probabilistic ...
user avatar
0 votes
0 answers
43 views

Definition of graph canonization and good textbook reference

I am struggling a bit with finding a good and generally accepted definition of graph canonization and canonical forms as well as a good textbook reference. From what I understand, a canonical form is ...
1 vote
1 answer
61 views

$n^2$-Grid $3n$-Coloring Game: Can we color a n-square grid with 3n colors s. t. we can't select n colors to get an histogram with $\Theta(n^2)$ area?

The coloring game is a game played between Alice and Bob. There exists a grid of size $n \times n$, where $n$ is a strictly positive integer. Each cell of the grid can be colored with a color that ...
user avatar
1 vote
1 answer
62 views

Edge sets on $\omega$ maximal with respect to chromatic number

If $H=(V,E)$ is a hypergraph, and $\kappa \neq \emptyset$ is a cardinal, a map $c: V\to \kappa$ is said to be a coloring if the restriction $c|_e: e\to \kappa$ is non-constant whenever $e\in E$ and $e$...
user avatar
3 votes
0 answers
167 views

Conjecture on connected hypergraphs

A hypergraph $H=(V,E)$ with $V$ non-empty is said to be connected if for all $S\subseteq V$ with $\emptyset \neq S \neq V$ there is $e\in E$ such that $e$ intersects both $S$ and $V\setminus S$. Given ...
user avatar
12 votes
3 answers
2k views

Is there any fast implementation of four color theorem in Python?

I'm now using scipy.spatial.Voronoi to generate a Voronoi graph, as shown here: voronoi graph. I'd like to apply the four color theorem on it, so that no adjcent regions share the same color. I ...
user avatar
  • 129
0 votes
1 answer
92 views

List coloring as a homomorphism

A proper coloring of the vertices of a graph $G$ is seen as a homomorphism from the graph vertices to the complete graph on the number of vertices equal to the chromatic number of the graph. ...
user avatar
  • 1,721
12 votes
0 answers
224 views

Computing the number of ways to delete vertices sequentially without disconnecting a graph

Given a finite connected graph on $n$ vertices, we are trying to count the number of ways to label the vertices $1$ to $n$ so that deleting them sequentially in that order never disconnects the graph. ...
user avatar
1 vote
1 answer
69 views

Chromatic number or independence number of the generalized Kneser Graph

For positive integers $n,k$ and $s$, where $0\le s<k$ and $k \le n$, we define the generalized Kneser graph $K(n,k,s)$ as follows: The vertices of $K(n,k,s)$ are the $k$-subsets of $[2n]$, i.e., we ...
user avatar
5 votes
1 answer
83 views

Is there any relationships between path cover number and chromatic number?

Let G be a finite simple graph. Consider the independent number $\alpha$, the chromatic number $\chi$ and the path cover number (also called the path partition number) $\rho$. Then we have $\alpha\chi ...
user avatar
  • 376
2 votes
1 answer
68 views

Efficient algorithm for edge-coloring complete graphs

Edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color with an optimal number of colors. Two edges are said to be adjacent if ...
user avatar
  • 1,002
1 vote
2 answers
104 views

Difference in chromatic number between Schreier coset graphs and Cayley graphs

Can the Schreier coset graphs can be seen as a subgraph of Cayley graph on the same groups(neglecting the loop edges) and, hence, have their chromatic numbers bounded by the chromatic numbers of the ...
user avatar
  • 1,721
0 votes
1 answer
41 views

Conflict-free coloring of linear hypergraphs on $\omega$

This question is motivated by considerations on conflict-free colorings, which arose while studying assignment problems for frequencies in cellular networks. A hypergraph $H=(V,E)$ is said to be ...
user avatar
2 votes
1 answer
96 views

Where can I find a picture of the complete 9-map on a triple torus that corresponds to Heffter’s table?

What I’m looking for is the analogue of Figure 5 in the paper by Saul Stahl, The Othe Map Coloring Theorem, Mathematics Magazine 1985, which is a complete 8-map $M_8$ on the double torus $S_2$ that ...
user avatar
3 votes
2 answers
276 views

Conflict-free coloring of $\mathbb{R}$ with the Euclidean topology

A hypergraph $H =(V, E)$ consists of a set $V$ and a set $E \subseteq {\cal P}(V)$ of subsets of $V$. A hypergraph coloring is a map $c: V\to \kappa$, where $\kappa \neq \emptyset$ is a cardinal and ...
user avatar
5 votes
1 answer
181 views

On the chromatic number of an analytic graph

Let $X$ be a Polish space and let $G\in\mathbf{\Sigma}^1_1(X^2)$ be a graph on $X$, that is an irreflexive and symmetric relation on $X$. Given a cardinal $\kappa$ we say that $G$ has chromatic number ...
user avatar
4 votes
4 answers
268 views

Subgraph avoiding colorings

Let $P_{H}(G, t)$ be the number of vertex colorings of a graph $G$ in $t$ colors that avoid having a monochromatic subgraph $H$. In particular, for $H$ given by a single edge we recover the usual ...
user avatar
7 votes
1 answer
189 views

Chromatic number and vertex connectivity

A conjecture of Mader implies that for any positive integer $n\geq2$, every graph with average degree at least $3n-4$ contains an $n$-connected subgraph. Mader himself proved this for $n=2,3,4,5,6,7$. ...
user avatar
0 votes
1 answer
99 views

Bound on chromatic number of graphs on any finite $p$-group

Is the chromatic number of a Cayley graph on $p$-groups with any generating set bounded by the chromatic number of the maximal induced circulant subgraph? I think yes. Because for one, the main ...
user avatar
  • 1,721
3 votes
0 answers
182 views

A form of Hadwiger's conjecture for hypergraphs

A hypergraph $H=(V,E)$ consists of a set $V$ and $E\subseteq {\mathcal P}(V)$. If $S\subseteq V$, we define $$E|_S = \{e\cap S: (e\in E) \land (e\cap S \neq \emptyset)\}$$ and call $(S, E|_S)$ the ...
user avatar
0 votes
1 answer
67 views

Extending the vertex coloring of circulant graph to graph on $p$-group

Let $G_1$ be a circulant graph of prime order $p$. This implies that $G_1$ is the Cayley graph on $\mathbb{Z}_p$ with some generating set $S_1$. I am interested in knowing the characterizations of the ...
user avatar
  • 1,721
1 vote
1 answer
197 views

Chromatic number of duals of uniform hypergraphs with large edges

Let $H=(V,E)$ be a hypergraph. If $\kappa>0$ is a cardinal, we say that $H$ is $\kappa$-uniform if $|e|=\kappa$ for all $e\in E$. If $X$ is a non-empty set, then a map $c:V\to X$ is said to be a ...
user avatar
1 vote
1 answer
118 views

Chromatic number and taking duals of hypergraphs

If $H=(V,E)$ is a hypergraph and $\kappa\neq \emptyset$ is a cardinal, then a map $c:V\to \kappa$ is said to be a colouring if for every edge $e\in E$ with $|e|\geq 2$ the restriction $c\restriction_e:...
user avatar
0 votes
0 answers
23 views

An edge has many colors on the edge colored graph

We know many properly colored problems, for example, properly colored hamilton path. If we admit that one edge has more than one colors, are there applications or similar research?
user avatar
1 vote
0 answers
54 views

Hadwiger number and minimal degree (II)

This is a follow-up on an older question. Suppose $G$ is a finite simple graph and $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$. Let $\delta(G)$ is the minimal degree of ...
user avatar
1 vote
0 answers
76 views

Proving $R(n_1+1,n_2+1,\cdots,n_k+1) \leq{n_1+n_2+\cdots+n_k \choose n_1,n_2,\cdots,n_k}$

The following statement is a well-known lemma of Ramsey number. $$R(m+1,n+1) \leq {m+n \choose m}$$ Now, I want to prove the improvement of the above statement: $$R(n_1+1,n_2+1,\cdots,n_k+1) \leq{n_1+...
user avatar
  • 321
21 votes
2 answers
995 views

The chromatic number of the union of two graphs

Let $G_n$ be the graph on the set of all binary strings of length $n$ with two strings adjacent whenever they are Hamming distance $2$ away from each other, or one of them lies below another one; thus,...
user avatar
  • 21.4k
4 votes
0 answers
62 views

Chromatic index of hypergraphs

A proper $k$-edge-coloring of a hypergraph $H$ is a mapping from $E(H)$ to a set of $k$ colors so that every pair of adjacent edges receives different colors. We say $H$ is $k$-edge-colorable if $H$ ...
user avatar
1 vote
1 answer
69 views

A sufficient condition for a subcuic graph having a 2-distance vertex 4-coloring

Let $G$ be a subcubic graph with only vertices of degree 1 or degree 3. Suppose that $G$ has an edge coloring $\varphi$ using colors from $\{1,2,3,4,5\}$ such that each edge is colored with a set of ...
user avatar
1 vote
1 answer
57 views

The equivalence of a kind of 2-fold edge coloring and the 2-distance vertex coloring for subcubic graphs

Let $G$ be a subcubic graph. Suppose that $G$ has an edge coloring $\varphi$ using colors from $\{1,2,3,4,5\}$ such that each edge is colored with a set of two elements from $\{1,2,3,4,5\}$ (e.g., $\...
user avatar
1 vote
1 answer
111 views

An equitable edge-coloring of bipartite graphs

In this book (I found it from other references, and it was a nice book to study.), there is an exercise that proving the following two statements. Every graph $G$ with $m$ edges and maximum degree $k$...
user avatar
  • 321
-1 votes
1 answer
70 views

Chromatic number of $(n, [n]^k)$

If $n\in\mathbb{N}$ is a non-negative integer, we consider it as a cardinal, so $n = \{0, \ldots, n-1\}$. If $X$ is a set, and $\kappa$ is a cardinal, we let $[X]^\kappa$ be the collection of subsets ...
user avatar
1 vote
1 answer
57 views

Pseudo-replication of a vertex in a perfect graph

Definition of 'replication of $v$' is Suppose $v \in V(G)$. Replication of $v$ is constructing $G'$ by adding a new vertex $v'$ such that $N_{G'}(v')=N_G(v) \cup \{v\}$. And the following statement ...
user avatar
  • 321
1 vote
1 answer
96 views

If $G$ and $H$ are $k$-critical, then applying Hajós construction to $G$ and $H$ makes $k$-critical graph

Here is the definition of Hajós construction. Let $G$ and $H$ be two undirected graphs, $vw$ be an edge of $G$, and $xy$ be an edge of $H$. Then the Hajós construction forms a new graph that combines ...
user avatar
  • 321
5 votes
1 answer
159 views

An inequality on the number of vertex colorings of planar graphs

Conjecture: Let $G$ be a simple maximal planar graph, and let $P(G,4)$ be the number of proper vertex colorings of $G$ with four colors. Let $v$ be a vertex of $G$ with degree ${\rm deg}(v)=5$, and ...
user avatar
1 vote
1 answer
79 views

$K_{k,m}$ is $k$-choosable if and only if $m<k^k$

This statement is proved by Vizing and Erdos & Rubin (page 30) independently. But I cannot find Vizing's paper (It's too old) and Erdos & Rubin's paper only says 'It is easily proved'. I ...
user avatar
  • 321
3 votes
1 answer
91 views

Proper graph colorings with similar sized color classes

In Grunbaum's paper, A result on graph coloring, the following conjecture was posed: Let $G$ be a graph with $n$ nodes with $\Delta(G) < k$. There exists a proper $k$-coloring $c:V(G)\to [k]$ such ...
user avatar
3 votes
1 answer
104 views

An edge coloring problem for class two graphs

A proper edge $k$-coloring of a graph is an assignment of $k$ colors to the edges of the graph so that no two adjacent edges have the same color. The smallest integer $k$ such that $G$ has a proper ...
user avatar
0 votes
1 answer
78 views

Two kinds of vertex-criticality

For any set $X$, we let $[X]^2 = \big\{\{x,y\}:x\neq y \in X\big\}$. If $G=(V,E)$ is a simple, undirected graph, and $v\in V$, let $N(v) = \{z\in V: \{v,z\}\in E\}$. Given any $v\in V$, we use the ...
user avatar
0 votes
1 answer
136 views

"Incompatible" pairs with respect to graph coloring

For any simple, undirected graph $G=(V,E)$, we denote by $\chi(G)$ the smallest cardinal $\kappa$ such that there is a coloring $c:V \to \kappa$. We say that $v\neq w\in V$ are incompatible if $\{v,w\}...
user avatar
0 votes
1 answer
40 views

Discrepancy of chromatic number and independent covering number for $k$-regular hypergraphs

If $H=(V,E)$ is a hypergraph and $\kappa \neq \emptyset$ is a cardinal, then a map $c:V\to\kappa$ is called a coloring if the restriction $c\restriction_e$ is non-constant for all $e\in E$ with $|e|\...
user avatar
7 votes
1 answer
312 views

Berge-Fulkerson conjecture --- the planar case

A well-known conjecture of Berge and Fulkerson says that every bridgeless cubic graph has a collection of six perfect matchings that together cover every edge exactly twice. Is this still open for ...
user avatar
  • 1,002
1 vote
0 answers
29 views

Are there known bounds on these ratios of chromatic polynomials?

The chromatic polynomial $P(G, \lambda)$ gives the number of proper vertex colorings of the graph $G$ with $\lambda$ colors. I'm interested in how many possible colorings you loose when you add an ...
user avatar
  • 111
8 votes
2 answers
600 views

Induced subgraphs of any given smaller chromatic number

Let $G = (V,E)$ be a simple, undirected graph with $\chi(G)$ infinite. Given a cardinal $\kappa$ with $0 < \kappa < \chi(G)$, is there an induced subgraph $S$ of $G$ with $\chi(S) = \kappa$? ...
user avatar
2 votes
1 answer
154 views

Is the union of a chain of $\kappa$-colorable subgraphs $\kappa$-colorable?

Motivation. I was trying to prove that whenever $G$ is a simple, undirected graph and $\kappa< \chi(G)$ is a cardinal, then there is an induced subgraph with chromatic number exactly $\kappa$. This ...
user avatar
1 vote
1 answer
188 views

What is this invariant graph?

Let $G$ be a simple graph (finite or infinite), $[n]\mathrel{:=}\{1,...,n\}$. Define the function: $$\varepsilon_n(G)\mathrel{:=}\min_\phi{\lvert{\operatorname{dom} (\phi)}\rvert},$$ where $\phi$ is ...
user avatar
  • 65
9 votes
0 answers
481 views

A perfect rainbow matching in an edge-colored graph with spanning color classes

This question is a sequel of my last question and is eventually motivated by recent advances in quantum physics. Given an even number $n\ge 6$ and a positive integer $k<n$, Claim from the linked ...
user avatar
  • 2,717
1 vote
1 answer
166 views

Coloring infinite graph made out of copies of a finite graph

I have an infinite graph $G^\infty$ constructed out of sequence $G_t$ of copies of some finite graph $G$. More specifically: Vertex set of $G^\infty$ is $$V(G^\infty) = \bigcup_{i \in \mathbb{Z}} V(...
user avatar
5 votes
0 answers
312 views

A special perfect matching in a complete edge-colored graph

In 2018 Mario Krenn posed this question, originated from recent advances in quantum physics. Despite very intensive Krenn’s promotion and our efforts, the question is answered only in special cases. ...
user avatar
  • 2,717

1
2 3 4 5
12