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
Filter by
Sorted by
Tagged with
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 ...
Andrew D. King's user avatar
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,...
Igor Pak's user avatar
  • 16.3k
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. ...
Mario Krenn's user avatar
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, ...
Dustin G. Mixon's user avatar
21 votes
0 answers
571 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 ...
Timothy Chow's user avatar
19 votes
0 answers
605 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 ...
Myshkin's user avatar
  • 17.4k
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 ...
Clive elphick's user avatar
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. ...
Dylan Thurston's user avatar
12 votes
0 answers
204 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 ...
Xin Zhang's user avatar
  • 1,130
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 ...
Gordon Royle's user avatar
  • 12.3k
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 ...
JonCC's user avatar
  • 211
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 ...
Alex Ravsky's user avatar
  • 4,092
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-...
Mario Krenn's user avatar
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, ...
NageebAli's user avatar
  • 101
9 votes
0 answers
303 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 ...
James Propp's user avatar
  • 19.4k
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 ...
Lviv Scottish Book's user avatar
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 ...
domotorp's user avatar
  • 18.3k
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 ...
domotorp's user avatar
  • 18.3k
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 ...
Florent Foucaud's user avatar
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 ...
John Machacek's user avatar
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 ...
David Harris's user avatar
  • 3,397
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-...
Florent Foucaud's user avatar
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 ...
Andrew D. King's user avatar
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. ...
Gejza Jenča's user avatar
6 votes
0 answers
406 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. ...
Alma Arjuna's user avatar
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 ...
EGME's user avatar
  • 1,008
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 ...
Taras Banakh's user avatar
  • 40.7k
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Jim Tilley's user avatar
6 votes
0 answers
350 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,...
Guilherme D. da Fonseca's user avatar
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,\...
Andrew D. King's user avatar
5 votes
0 answers
110 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 ...
Per Alexandersson's user avatar
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 ...
CTVK's user avatar
  • 151
5 votes
0 answers
102 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$ ...
W. Paul Liu's user avatar
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)$ ...
Dominic van der Zypen's user avatar
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 ...
Joseph O'Rourke's user avatar
5 votes
0 answers
165 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 ...
Dominic van der Zypen's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
David Harris's user avatar
  • 3,397
4 votes
0 answers
202 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 ...
bof's user avatar
  • 11.5k
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,...
Thomas Haettel's user avatar
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 ...
Alex Golovnev's user avatar
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 (...
Darren Ong's user avatar
4 votes
0 answers
58 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) (...
PartonWavicle's user avatar
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 ...
Gerry Myerson's user avatar
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. ...
M. Winter's user avatar
  • 12.5k
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}$ ...
Dominic van der Zypen's user avatar
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$ ...
Dominic van der Zypen's user avatar
4 votes
0 answers
79 views

Complexity of counting colorings of co-bipartite graphs?

A graph is co-bipartite if it is the complement of bipartite graph. What is the complexity of counting colorings of co-bipartite graphs? Unlike split graphs, the chromatic polynomial isn't of ...
joro's user avatar
  • 24.2k