Questions tagged [graph-colorings]
Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.
177
questions with no upvoted or accepted answers
51
votes
0
answers
2k
views
Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?
A very specific case of Reed's Conjecture
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 ...
36
votes
0
answers
1k
views
3-colorings of the unit distance graph of $\Bbb R^3$
Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$.
Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = (\alpha,...
32
votes
0
answers
3k
views
Vertex coloring inherited from perfect matchings (motivated by quantum physics)
Added (19.01.2021): Dustin Mixon wrote a blog post about the question where he reformulated and generalized the question.
Added (25.12.2020): I made a youtube video to explain the question in detail.
...
24
votes
0
answers
744
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, ...
21
votes
0
answers
572
views
Coloring a Ferrers diagram
I've shopped the problem below around a bit and it seems like it might be known, or not that hard to resolve, but so far I've come up empty-handed.
Say that a coloring of the dots of a Ferrers ...
19
votes
0
answers
606
views
Simpler proofs of certain Ramsey numbers
The reason for the gorgeous simplicity of the classic proofs of $R(3,3)$, $R(4,4)$, $R(3,4)$ and $R(3,5)$ is that essentially all you need is the trivial bound and a picture.
But for bigger Ramsey ...
13
votes
0
answers
1k
views
A new lower bound for the chromatic number of a graph?
Let $S_{+}(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph $G$. Let $S_{-}(G)$ denote the sum of the squares of the negative eigenvalues and $q$ the ...
12
votes
0
answers
253
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. ...
12
votes
0
answers
206
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 ...
12
votes
0
answers
448
views
Colouring a graph whose edge set is a special union of cliques
I am trying to show that a certain family of graphs can always be properly coloured with at most $6$ colours (where "properly coloured" means that each vertex gets a colour and no edge has both ends ...
11
votes
0
answers
225
views
Is there a term for this graph subset?
Suppose $G$ is a (finite) graph which is $k$-vertex colourable (i.e. $\chi(G)\leqslant k$). Suppose $S$ is a set of vertices of $G$ with the following property:
If $c:V(G)\rightarrow [k]$ is a vertex ...
10
votes
0
answers
607
views
A rainbow perfect 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 ...
10
votes
0
answers
715
views
Has this notion of vertex-coloring of graphs been studied?
In a study of a quantum physics problem, I came about an apparently very natural type of vertex colorings of a graph. The colors of the vertex $v_i$ is inherited from perfect matchings $PM$ of an edge-...
10
votes
0
answers
302
views
Among regular graphs, do cliques have the highest infection rate?
Consider a graph $G$ with a particular node $i$ labeled as “infected”. Other nodes start uninfected, and will become infected over time according to the following process: To each edge of the graph, ...
9
votes
0
answers
307
views
Goldberg-Seymour conjecture
I am wondering whether the graph theory community regards the Goldberg-Seymour conjecture as settled. According to the Wikipedia entry on the Goldberg-Seymour conjecture, "In 2019, an alleged ...
9
votes
0
answers
154
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 ...
8
votes
0
answers
262
views
Does hereditary 2-coloring imply polychromatic 3-coloring for large edges?
For a hypergraph $\mathcal H=(V,\mathcal E)$, denote by $m_k$ the smallest number for which we can $k$-color any $X\subset V$ such that for any $E\in \mathcal E$ with $|E\cap X|\ge m_k$ all $k$ colors ...
8
votes
0
answers
63
views
Color edges of graph w/r/t large induced subgraphs
Can we color the edges of any graph $G$ on $2m-1$ vertices with two colors such that any induced subgraph with at least $m$ edges is non-monochromatic?
If true, this would be sharp as shown by the ...
8
votes
0
answers
149
views
Edge-colorings of plane graphs: do you know references where the following questions are studied?
Let $G$ be a plane graph (or more generally, a graph embedded on a surface) with a proper edge-coloring of $G$ with $k$ colors $\{1,\ldots,k\}$. I am interested in studying the cyclic permutations of ...
7
votes
0
answers
93
views
What is known about chromatic polynomial of hypergraph at $-1$
Let $H$ be a hypergraph and let $P_H$ denote its chromatic polynomial. I am interested in the best results interpreting $P_H(-1)$. I am interested both in the general case (which I think is hard) as ...
7
votes
0
answers
213
views
Bound on chromatic number for a class of graphs
Consider a triangle-free graph $G$, in which the vertices are partitioned in blocks $V = A_1 \sqcup \dots \sqcup A_k$.
$G$ has the property that, for each $i \leq j$, each vertex in $A_i$ has at most ...
7
votes
0
answers
223
views
The smallest order of a 4-chromatic graph of given girth
Let $n_4(g)$ denote the smallest order of a $4$-chromatic graph with girth $g$. It is known that $n_4(4)=11$ [2] and $n_4(5)=21$ [1]. By a famous proof of Erdös, it is known that $n_4(g)$ is well-...
7
votes
0
answers
472
views
Maximum fractional chromatic number of a 4-regular triangle-free graph (updated)
Let $G$ be a graph with maximum degree 4 and clique number 2. The fractional version of Reed's Conjecture tells us that $\chi_f(G) \leq 7/2$. But how high can $\chi_f(G)$ be?
The Chvátal graph has ...
7
votes
0
answers
396
views
What is this subclass of $k$-colorable graphs called?
The following property emerged naturally when I was playing with certain generalizations of Kneser graphs.
Let $k>0$ be a natural number. Consider a property $P_k$ of graphs defined as follows.
...
6
votes
0
answers
408
views
Example of graph with strange property
I've also posted this problem in Math Stack Exchange (here).
Note: Whenever I mention a coloring of a graph I'm referring to a proper coloring over its vertices using the least amount of colors.
...
6
votes
0
answers
73
views
Normal colorings of bridgeless cubic graphs
Definition (informal) A normal edge-5-coloring of a bridgeless cubic graph $G$ is a proper 5 coloring of the edges of the graph, so that for each edge $e\in E(G)$, either $e$ and the four edges ...
6
votes
0
answers
107
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 ...
6
votes
0
answers
128
views
Edge-coloring number of a linear hypergraph
A linear hypergraph is a hypergraph $H=(V,E)$ such that
$|e|\geq 2$ for all $e\in E$,
$|e_1\cap e_2|\leq 1$ for all $e_1, e_2\in E$ with $e_1\neq e_2$.
An edge coloring of $H$ is a function $c:E\to ...
6
votes
0
answers
139
views
Doubly edge-contraction critical graphs
Is there a simple undirected, connected, non-complete graph $G=(V,E)$ with at least $2$ edges, such that the following condition holds?
Whenever you contract $1$ or $2$ edges, the resulting ...
6
votes
0
answers
116
views
Chromatic numbers for coloring-constrained graphs
I am interested in any and all articles about chromatic numbers applying to constrained colorings of a graph. For example, if a graph must be (properly) colored so that there is a 2-color path ...
6
votes
0
answers
352
views
Independence Number of K4-free planar graphs
The independence ratio is defined as the size of the maximum independent set divided by $n$. By the 4-color theorem, every planar graph with $n$ vertices has independence ratio at least $1/4$. Clearly,...
6
votes
0
answers
300
views
A maximum discrepancy hypergraph 2-colouring problem
This is sort of a hypergraph-ish question that I feel should be easy to prove or disprove but I can't see it right now.
The setup is as follows. We have a vertex set partitioned in to sets $V_1,\...
5
votes
0
answers
116
views
If chromatic polynomials for two graphs agree, can I always find an edge such that the two deletion-contraction minors have same chromatic polynomial?
Suppose I have non-isomorphic graphs $G$ and $H$ (which have at least one edge), but such that their chromatic polynomials are the same. Can I then always find an edge $e$ in $G$ and $f$ in $H$ such ...
5
votes
0
answers
71
views
Is the choosability/list chromatic number of a circular arc graph equal to its chromatic number?
In 2003, Prowse and Woodall proved that for graphs $C_n^k$ which are powers of cycles,
$$\chi_\ell(C_n^k) = \chi(C_n^k).$$
They conjectured that this equality holds for the broader class of graphs ...
5
votes
0
answers
104
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$ ...
5
votes
0
answers
178
views
Graph of number pairs summing to a square number
Consider the set $\mathbb{Z}_+$ of positive integers and set $E = \big\{\{a,b\}: a\neq b\in\mathbb{Z}_+ \text{ and there is } n\in\mathbb{Z}_+: a+b = n^2\big\}$.
Does the graph $G=(\mathbb{Z}_+,E)$ ...
5
votes
0
answers
117
views
Equitable 4-colorings of planar triangulations
In an
equitable coloring
of a graph $G$, the number of vertices in each color class differ
by at most $1$.
For example, left below is not an equitable coloring, while the
right graph is equitably ...
5
votes
0
answers
166
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 ...
5
votes
0
answers
101
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 ...
5
votes
0
answers
147
views
Fractional chromatic number for triangle-free d-degenerate graphs
The following statement seems very plausible:
If $G$ is a triangle-free graph of degeneracy $d$, then
$$
\chi_f(G) \leq O(\frac{d}{\log d})
$$
where $\chi_f$ is the fractional chromatic number.
This ...
4
votes
0
answers
214
views
Optimal colorings
If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$.
For any coloring $c:V(G) \...
4
votes
0
answers
203
views
The list reaping number?
My question is inspired by a question of Dominic van der Zypen. Let $[\omega]^\omega$ denote the set of all infinite subsets of $\omega$.
The reaping number, denoted by $\mathfrak r$, is the minimum ...
4
votes
0
answers
41
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,...
4
votes
0
answers
113
views
Faithful Orthogonality Dimension of Kneser Graphs
Let us consider the complement of the Kneser graph with parameters $n$ and $n/4$. The vertex set of our graph $K$ is the set $\binom{[n]}{n/4}$ of $n/4$-subsets of $[n]$, and two vertices are joined ...
4
votes
0
answers
70
views
Unbalanced colourings of Penrose tiles
It is known that both the rhombus and kite-and-dart Penrose tilings are three-colourable, from
Babilon, Robert. "3-colourability of Penrose kite-and-dart tilings." Discrete Mathematics 235, no. 1-3 (...
4
votes
0
answers
59
views
Bipartite graphs with alternating edge colorings
I would like to find all graphs or lattices which satisfy the following conditions:
(1) Graph is bipartite with vertex types $A$ and $B$ ($A$-vertices only connected to $B$-vertices and vice-versa)
(...
4
votes
0
answers
179
views
Deletion-contraction versus addition-identification
I posted this question to math.stackexchange in 2016. No answers were forthcoming [EDIT: the question has now been answered on math.stackexchange!], even after I put a bounty on the question, so ...
4
votes
0
answers
226
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. ...
4
votes
0
answers
218
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}$ ...
4
votes
0
answers
116
views
Infinite $3$-chromatic hypergraphs
Let $H=(V,E)$ be a hypergraph. If $\kappa>0$ is a cardinal, we say the hypergraph $H$ is $\kappa$-chromatic if there is a function $c:V\to\kappa$ such that for all $e\in E$ the restriction $c|_e$ ...