Questions tagged [graph-colorings]
Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.
623
questions
2
votes
0
answers
108
views
List total chromatic number of complete graphs
Since for an odd integer $n$, a complete graph on $n$ vertices is list-edge-$n$ choosable, and the total chromatic number is $n$, it is easy to see that the list total chromatic number is bounded ...
3
votes
1
answer
199
views
Chromatic number of a family of graphs
It is well-known that if a graph has maximum degree $d$, then it is $d+1$ colorable. Say we have $d+1$ graphs $G_1,\ldots, G_{d+1}$ on the same vertex set $V$, and say each $G_i$ has maximum degree at ...
3
votes
1
answer
265
views
Evans conjecture for symmetric latin squares
The Evans conjecture ( which was proved later by Smetaniuk) states that for any $n$, if at most $n-1$ entries of a partial $n\times n$ latin square are filled, it can be completed to the full latin ...
0
votes
0
answers
113
views
Procedure to color the edges of a circulant graph
From the first theorem in this paper, it is clear that a cayley graph on abelian group for all generating sets of even order is class $1$, that is can be edge colored in exactly $\Delta$ colors. But, ...
6
votes
1
answer
161
views
Embedding any graph into a vertex-transitive graph of the same chromatic number
If $G=(V,E)$ is a simple, undirected graph, is there a vertex-transitive graph $G_v$ such that $\chi(G) = \chi(G_v)$ and $G$ is isomorphic to an induced subgraph of $G_v$?
1
vote
0
answers
101
views
Kernel perfect orientations of complete graphs
How can we create a kernel perfect orientation of a complete graph? A kernel of a graph is a set of vertices in a graph $G$, which absorbs other vertices, that is, has all the vertices in its ...
1
vote
0
answers
112
views
If choosability of complement is known, can the choosability of the graph be known?
Suppose, we know that $G$ is a regular graph of odd order that is $k$- edge choosable, where $k$ is the degree. Then, is it true that $\overline{G}$ has list edge chromatic number at most $n-k+1$?
I ...
2
votes
1
answer
85
views
List coloring of a graph corresponding to a Steiner triple system
Consider the Steiner triple system $S(2,3,n)$ for a suitable integer $n$. We define a graph $G$ with all the vertices as precisely the blocks of the above steiner triple system and any two points ...
4
votes
1
answer
199
views
Embedding any graph in a regular graph with the same chromatic number
If $G=(V,E)$ is a simple, undirected graph, is there a regular graph $G_R$ such that $G$ is isomorphic to an induced subgraph of $G_R$ and $\chi(G) = \chi(G_R)$?
6
votes
1
answer
177
views
On a limit involving a transform of the chromatic polynomial
I was playing around with the chromatic polynomial (denoted here by $\chi_G(x)$) and I have made the following conjecture.
Let $(G_n)_{n \ge 1}$ be a sequence of graphs with $v(G_n) \to \infty$ ($v(...
3
votes
1
answer
344
views
Graph which is maximal triangle-free 3-colorable, but not maximal triangle-free
I am looking for a graph which is maximal triangle-free 3-colorable, but not maximal triangle-free. Here a graph which is maximal triangle-free 3-colorable is a graph where the addition of any edge ...
4
votes
1
answer
173
views
Are K_t-minor free graphs on small vertex sets understood?
In a paper on Hadwiger's conjecture, https://web.math.princeton.edu/~pds/papers/hadwiger/paper.pdf, Seymour explains various results on excluding the complete graph as a minor.
In particular, there is ...
3
votes
1
answer
322
views
Does every maximal almost disjoint family have the same chromatic number?
If $H=(V,E)$ is a hypergraph such that $V\neq\varnothing\neq E$ and $|e| > 1$ for all $e\in E$, and $\kappa\neq\varnothing$ is a cardinal, we say that a map $c:V\to\kappa$ is a coloring if the ...
1
vote
2
answers
210
views
Hedetniemi for pseudo-chromatic number $\psi(G)$
Let $G=(V,E)$ be a finite simple graph. We say a map $p:V\to [n]:=\{1,\ldots,n\}$ is a pseudo-coloring if for all $a\neq b\in[n]$ there is $v\in\psi^{-1}(\{a\})$ and $w\in\psi^{-1}(\{b\})$ such that $\...
3
votes
0
answers
142
views
Chromatic number of regular graphs using spectra
There exist inequalities relating the maximum and minimum eigenvalues of the adjacency matrix of a graph with its chromatic numbers, i.e. the Wilf's and Hoffmann's inequalities, which put together ...
6
votes
1
answer
247
views
List chromatic index of a particular graph
Consider the graph $G$ of order $n$ consisting of two disjoint cliques of even order $\frac{n}{2}=p+1$ (where $p$ is odd prime) joined by a bipartite graph (that is, deleting the edges of the two ...
0
votes
1
answer
132
views
Decomposition of regular graphs
Let $G$ be a regular simple graph with degree $\Delta=n-k-1$ and order $m$. Let $C_k$ be the regular graph which is formed by removing a $k$-factor from the complete graph $K_{n}$. I think we could ...
2
votes
2
answers
215
views
The edge precoloring extension problem for complete graphs
Consider coloring the edges of a complete graph on even order. This can be seen as the completion of an order $n$ symmetric Latin square except the leading diagonal. My question pertains to whether we ...
0
votes
0
answers
113
views
Vertex cover algorithm
Given a graph $G(V, E)$, remove the vertex (or one of the vertices) with the highest cardinality from $G$ and put it in a list $L$. Repeat until in $G$ there are only vertices with cardinality $0$ (no ...
11
votes
1
answer
355
views
Graph chromatic numbers defined by interactive proof
Edit (2020-07-15): Since the discussion below is perhaps a bit long, let me condense my question to the following
Short form of the question: Let $G$ be a finite graph (undirected and without self-...
1
vote
0
answers
132
views
The chromatic polynomial of a line graph
Is there a way to obtain the chromatic polynomial of the line graph of a regular simple graph, having known the chromatic polynomial of the graph?
There already exist characterizations of line graph ...
2
votes
1
answer
215
views
Non-conformity colorings
Motivation. Recently I attended a little party (adhering to physical distancing and in accordance to other COVID19-related laws). An attendee told me that he chose drink $Y$ since at least half of his ...
0
votes
1
answer
173
views
Relationship between cycle length, number of chords, and number of induced $P_{4}$ subgraphs of the cycle
I was wondering if there was a known relationship between the length of cycle, the number of chords of the cycle, and the number of induced $P_{4}$ subgraphs of the cycle.
Here, I am referring to ...
0
votes
1
answer
116
views
Relaxing Meyniel graphs: condition for strongly perfect instead of very strongly perfect
A Meyniel graph, $\mathcal{G}$ is a graph in which every cycle of odd length at least 5 has at least 2 chords.
First off, I have a technical question which is very important to me:
what is meant by ...
1
vote
1
answer
121
views
Bound on the chromatic number of square of bipartite graphs
In continuation of the previous question, what is a strict upper bound on the chromatic number of the square of a bipartite graph?
I think the chromatic number number of the square of the bipartite ...
3
votes
1
answer
413
views
Chromatic number of square of a tree
What is an upper bound on the chromatic number of the square of a tree on $n$ vertices? Note that the power of the graph is considered in this sense.
If the tree were a path, then it is easy to see ...
6
votes
1
answer
369
views
Probability in Chromatic number upper bound of induced subgraph
Let $G=(V, E)$ be a graph with chromatic number $\chi(G)=1000 .$ Let $U \subset V$ be a random subset of $V$ chosen uniformly from among all $2^{|V|}$ subsets of $V$. Let $H=G[U]$ be the induced ...
6
votes
2
answers
842
views
3-colored triangulations of the sphere $S^2$, and Sperner's Lemma
I noticed something about colored triangulations of the topological sphere $S^2$ and have a question about this.
Observation. If you triangulate the sphere $S^2$ and color the vertices with three ...
0
votes
1
answer
58
views
Minimal and maximal degrees in critical graphs
Let $G=(V,E)$ be a finite simple undirected graph. We say that $G$ is critical if for all $v\in V$ we have $$\chi(G\setminus\{v\}) < \chi(G).$$ By $\Delta(G)$ and $\delta(G)$ we denote the maximum ...
4
votes
1
answer
137
views
Chromatic number of regular linear hypergraphs on $\omega$
For any cardinal $\alpha \in \omega\cup \{\omega\}$, let $[\omega]^\alpha$ denote the collection of subsets of $\omega$ having cardinality $\alpha$.
A linear hypergraph $H=(V,E)$ is a hypergraph such ...
3
votes
0
answers
189
views
Clique cover number of a generalized Kneser graph $K(n,4,2)$
Recently I attacked this combinatorial question. The value of $m(n)$ introduced in it equals to a clique cover number
of a generalized Kneser graph $KG_{n,4,1}=K(n,4,2)$ (or the chromatic number of ...
2
votes
1
answer
250
views
Independent sets in complement of Kneser graphs
Intuition strongly suggests that there exist $\left\lfloor\frac{\binom{n}{k}}{\lfloor\frac{n}{k}\rfloor}\right\rfloor$ independent sets in the complement of a Kneser graph each having $\lfloor\frac{...
5
votes
1
answer
394
views
What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?
Also asked on MSE: What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?.
Consider the set $X = \{1,2,3,\dots,n\}$. Define the collection of all $4$-subsets of $X$ by $$\mathcal A=...
0
votes
0
answers
67
views
Hypergraph coloring in linear hypergraphs
Let $H=(V,E)$ be a hypergraph with $V\neq\varnothing$ and $E \neq \varnothing$ such that
for all $e\in E$ we have $|e|\geq 2$, and
for all $e\neq e_1 \in E$ we have $|e\cap e_1|\leq 1$.
Is there a ...
3
votes
1
answer
145
views
Structure of boundary labelling in Sperner‘s Lemma
Consider a triangulated polygon in the 2-dimensional plane, where each vertex is labelled green, blue, or orange. Sperner's Lemma asserts that a fully-colored triangle exists in the triangulation, if ...
3
votes
1
answer
72
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
1
answer
131
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
74
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
90
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\...
1
vote
2
answers
94
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 ...
24
votes
1
answer
565
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
1
answer
160
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
210
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
84
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
1k
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
52
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
53
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
186
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 ...
0
votes
1
answer
40
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
96
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 ...