Questions tagged [graph-colorings]
Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.
568
questions
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 ...
- 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 ...
- 128
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 ...
- 11
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$...
- 39.7k
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 ...
- 39.7k
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 ...
- 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. ...
- 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. ...
- 9,875
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 ...
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 ...
- 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 ...
- 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 ...
- 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 ...
- 39.7k
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 ...
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 ...
- 39.7k
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 ...
- 2,059
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 ...
- 547
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$. ...
- 123
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 ...
- 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 ...
- 39.7k
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 ...
- 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 ...
- 39.7k
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:...
- 39.7k
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?
- 33
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 ...
- 39.7k
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+...
- 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,...
- 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$ ...
- 463
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 ...
- 463
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., $\...
- 463
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$...
- 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 ...
- 39.7k
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 ...
- 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 ...
- 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 ...
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 ...
- 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 ...
- 937
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 ...
- 463
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 ...
- 39.7k
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\}...
- 39.7k
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|\...
- 39.7k
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 ...
- 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 ...
- 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$?
...
- 39.7k
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 ...
- 39.7k
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 ...
- 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 ...
- 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(...
- 119
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. ...
- 2,717