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
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
3 votes
0 answers
204 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) \...
Dominic van der Zypen's user avatar
5 votes
1 answer
183 views

Chromatic number of the infinite Erdős–Hajnal shift-graph

For any set $X$, let $[X]^2= \big\{\{x,y\}: x\neq y \in X\big\}$. Let $\kappa$ be an infinite cardinal. Let $G_\kappa = ([\kappa]^2, E_\kappa)$ where $E_\kappa = \big\{\{a,b\}\in \big[[\kappa]^2\big]^...
Dominic van der Zypen's user avatar
3 votes
1 answer
106 views

Chromatic number of triangle-free graph $[[n]]^2$ with edges of form $a<b, b<c$

I am reading (and enjoying!) Bela Bollobas' book "Modern Graph Theory", and one of the exercises shows how to construct triangle-free graphs with large chromatic number: For any non-negative ...
Dominic van der Zypen's user avatar
1 vote
1 answer
101 views

A reliable reference for the statement every $k$-tree is uniquely $(k + 1)$-colorable

I see that every $k$-tree is uniquely $(k + 1)$-colorable in Uniquely_colorable_graph. Wikipedia does not cite any references, even though I know that its proof is not difficult by using mathematical ...
L.C. Zhang's user avatar
  • 1,605
2 votes
2 answers
66 views

Reference request for a subfamily of regular graphs

[Repost of same question math stack exchange which got no answers] I'm looking for literature on the following family of graphs: Call a regular graph $G=(V,E)$ (of regularity degree $d$) nice if there ...
jojo's user avatar
  • 21
2 votes
1 answer
94 views

Exhaustive list of small graphs for which $\frac{\alpha(G)\omega(G)}{n}$ is small?

I am looking for a list of small graphs (say on less than 10 vertices) for which the parameter $p(G) = \frac{\alpha(G) \omega(G)}{n}$ is small. Here $\alpha(G)$ and $\omega(G)$ is the size of the ...
Agile_Eagle's user avatar
1 vote
1 answer
108 views

A bound on the number of partial transversals of a latin square

A Latin Square (LS) of order $n$ is an $n$ on $n$ matrix, each entry contains one of the symbols $1,2,\ldots,n$, and every row and every column contains each symbol exactly once. A (complete) ...
John's user avatar
  • 161
0 votes
0 answers
38 views

Determining homomorphism using automorphism group of two graphs

I wish to know the connection between the automorphism group of two graphs and homomorphism between them, if any. Like all Kneser graphs $K(n,k)$ have the same automorphism group $S_n$. But, given ...
vidyarthi's user avatar
  • 2,007
1 vote
1 answer
233 views

Choosing sets with a few properties from a given set of elements

Fix $n$ and $k$ with $n \geq 2k+1$. Let $X$ be an $n$ element set. Let $\binom{X}{k}$ denote the collection of $k$-element subsets of $X$. Suppose that $\mathcal{Y} \subseteq \binom{X}{k}$ is a family ...
vidyarthi's user avatar
  • 2,007
3 votes
1 answer
139 views

Does every graph admit an embedding such that identically-colored edges do not cross?

Given a graph, is it always possible to color the edges of the graph using two colors such that there exists an embedding of the graph in the plane where only opposite-colored edges cross? Simple ...
Tjaden Hess's user avatar
0 votes
0 answers
49 views

Kernel perfection in some powers of cycles

Suppose I orient the edges of the power of cycle graph $G=C_n^k$ where $n=16$ and $k=4$ in such a way that all the generated cycles by the elements $1,2,3,4$ are given the standard lexical orientation....
vidyarthi's user avatar
  • 2,007
1 vote
1 answer
195 views

Connected vertex-transitive graphs of fixed chromatic number and arbitrary size

A simple, undirected graph $G=(V,E)$ is said to be vertex-transitive if for all $v,w\in V$ there is a graph isomorphism $\varphi:V\to V$ such that $\varphi(v) = w$. The cyclic graphs $C_{2n+1}$ are ...
Dominic van der Zypen's user avatar
1 vote
1 answer
150 views

Gentle(-er) Introduction to Erdős–Bollobás's solution to Ramsey–Turán Type Problem

I am currently trying to understand the construction of maximal graph which contains no $K_4$ and sub-linear number of independent points in the graph. The original paper On a Ramsey–Turán type ...
total dependent random choice'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
0 votes
0 answers
78 views

Is there is a constant $c$ such that toroidal graphs are minor-$c$-colorable?

A toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross. A minor of graph G is a graph obtained from G by ...
Xin Zhang's user avatar
  • 1,130
3 votes
1 answer
223 views

Sum of squares of chromatic roots of a bipartite graph

Given a graph $G = (V, E)$, we can calculate its chromatic polynomial $P(G, k)$, and it has $n$ (complex) roots, also known as chromatic roots. It is a well-known fact that the sum of chromatic roots ...
hedgehog0's user avatar
2 votes
1 answer
124 views

Clique number of $k$-critical graphs

A graph $G$ is called a ${\it{k}}$-${\it{critical}}$ graph if $\chi(G)=k$ and for any proper subgraph $H$ of $G$ we have $\chi(H)<k$, where $\chi(G)$ denotes the chromatic number of $G$. The ...
CCC's user avatar
  • 41
1 vote
0 answers
63 views

Colorability classes of graphs

Let $G=(V,E)$ be a simple, undirected graph, finite or infinite, with $V \neq \emptyset$. We consider the chromatic number $\chi(G)$ as a cardinal. We say that colorings $c:V\to \chi(G)$ are proper ...
Dominic van der Zypen's user avatar
15 votes
1 answer
1k views

Parity and the Axiom of Choice

Motivation. The three-dimensional cube can be formalized by $\mathcal P(\{0,1,2\})$ where vertices $x,y\in\mathcal P(\{0,1,2\})$ are connected by an edge if and only if their symmetric difference $x\...
Dominic van der Zypen's user avatar
2 votes
1 answer
85 views

Is the Hadwiger-Nelson graph restricted to $\mathbb{Q}\times\mathbb{Q}$ bipartite?

Consider the graph on $\mathbb{Q}\times\mathbb{Q}$ where two members of $\mathbb{Q}\times\mathbb{Q}$ form an edge if and only if their distance is $1$. Is that graph bipartite? If not, what is its ...
Dominic van der Zypen's user avatar
0 votes
1 answer
100 views

Hadwiger number of the Hadwiger-Nelson graph on $\mathbb{R}^2$

If $G =(V,E)$ is a simple, undirected graph (finite or infinite), and $\kappa \neq \emptyset$ is a cardinal, we say that the complete graph $K_\kappa$ is a minor of $G$ if there is a collection ${\...
Dominic van der Zypen's user avatar
1 vote
2 answers
124 views

Constants for diagonal hypergraph Ramsey Theorem

For integers $n,s$, we write $K_n^{(s)}$ to denote the complete $s$-uniform hypergraph on $n$ vertices. Given integers $k,s,r$, let $R(K_k^{(s)};r)$ denote the smallest $N$ such that, for every $r$-...
Zach Hunter's user avatar
  • 3,375
3 votes
1 answer
120 views

The sequence of the power chromatic numbers $(\chi(G^n))_{n\in\mathbb{N}}$

For any finite, simple, undirected graphs $G, H$ we denote by $G\times H$ their categorical product. For any graph $G$ we let $G^1 = G$ and for $n\geq 1$ we let $G^{n+1} = G \times G^n$. It is easy to ...
Dominic van der Zypen's user avatar
0 votes
3 answers
123 views

Even regular planar graphs without 2-cycles

Related to another question I asked, some questions came up, the most important is the following: Are there any 4-regular planar graphs without 2-cycles + 3-cycles? Could someone draw an example if ...
Kregnach's user avatar
0 votes
0 answers
69 views

Perfect graphs are normal graph

Let $G$ be a graph. We call $G$ normal if it admits two partitions: $V(G)=\bigcup \mathcal{I}=\bigcup \mathcal{C}$ where $\mathcal{I}$ is a collection of independent sets and $\mathcal{C}$ is a ...
Isomorphism's user avatar
0 votes
0 answers
39 views

Is it always possible to create a minimum depth tree where tree nodes are unique and have a 'choice'?

This is a somewhat long question thus sincere apologies beforehand. In a tree a node is a simple point. Now instead of a node let us consider a set of 'choice nodes' that have the following properties:...
J.Doe's user avatar
  • 101
2 votes
1 answer
65 views

Possible chromatic numbers of a hypergraph on $\omega$ with a deck of edges

Let $\omega$ denote the first infinite ordinal (also known as the set of natural numbers). We call a set $E\subseteq {\cal P}(\omega)$ a deck if for all $n\in \omega$, the set $E$ contains exactly one ...
Dominic van der Zypen's user avatar
1 vote
0 answers
73 views

Constructing orientations that increase (directed) distances between vertices in a maximum independent set

An orientation of a simple undirected graph $G=(V,E)$ is a directed graph $G' = (V,E')$ that is constructed by including either $(u,v) \in E'$ or $(v,u) \in E'$, but not both, for all $(u,v) \in E$. ...
fawadria's user avatar
1 vote
0 answers
59 views

Correct dependence for "Local Coloring"

In Alon-Spencer's book, Probabilistic Lens #8, it is proven that for each $k$, there exists $\epsilon = \epsilon(k)>0$ such that for all large $n$, there exists an $n$-vertex graph $G$ with ...
Zach Hunter's user avatar
  • 3,375
20 votes
2 answers
1k views

Non-definability of graph 3-colorability in first-order logic

What is a proof that graph 3-colorability is not definable in first order logic? Where did it first appear?
Leo Marcus's user avatar
1 vote
1 answer
159 views

Edge-colored flat graphs

Say that an undirected graph without loops or multiple edges is $n$-colored if its edges are labelled with numbers in $\{ 1, \ldots, n \}$ so that adjacent edges have different labels. Theorem [Alon-...
asd's user avatar
  • 11
1 vote
1 answer
124 views

Is the chromatic number of hypergraphs downward continuous?

Let $H=(V,E)$ be a hypergraph. The chromatic number $\chi(H)$ is the smallest cardinal $\kappa \leq |V|$ such that there is a map $c:V\to \kappa$ such that for all $e\in E$ having more than one ...
Dominic van der Zypen's user avatar
1 vote
1 answer
46 views

Hamiltonian edge colouring of complete graphs with even numbers of vertices

Edges of the complete graph on $2n$ vertices can be colored with $2n-1$ colors such that only edges of different colors intersect. Can this always be done such that for every pair of different colors ...
Roland Bacher's user avatar
6 votes
0 answers
405 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
2 votes
0 answers
119 views

A variation of packing chromatic numbers for $\mathbb Z^d$

Subercaseaux and Heule showed in https://arxiv.org/abs/2301.09757 (The Packing Chromatic Number of the Infinite Square Grid is 15) that $n=15$ is the smallest positive integer for which there is a map ...
Roland Bacher's user avatar
3 votes
1 answer
100 views

Edge coloring of a graph on alternating groups

Let $G$ be the Cayley graph on the alternating group $A_n\,n\ge4$ with generating set $$S=\begin{cases}\{(1,2,3),(1,3,2),\\(1,2,\ldots,n),(1,n,n-1,\ldots,2)\}, &n\ \text{odd}\\ \{(1,2,3),(1,3,2),\\...
vidyarthi's user avatar
  • 2,007
1 vote
0 answers
67 views

4CT for infinite aperiodic planar graphs [duplicate]

Inspired by the recent Einstein 'Hat' tiling. Is Appel & Haken's proof still applicable to an infinite aperiodic graph ? Such a graph with 1 region less still remains an infinite graph, right? How ...
P.Labarque's user avatar
14 votes
5 answers
1k views

How can one construct a four-coloring of a tiling of the plane with Smith, Myers, Kaplan, and Goodman-Strauss's aperiodic monotile?

This is motivated by the new paper of Smith, Myers, Kaplan, and Goodman-Strauss, wherein they define the existence of an aperiodic monotile. Clearly their tiling is not three-colorable, so we have ...
Lucas Blakeslee's user avatar
34 votes
1 answer
3k views

Can we three-color a tiling of the plane with Smith, Meyers, Kaplan, and Goodman-Strauss's einstein?

The tiling world is a bit aflutter recently with the drop of Smith, Meyers, Kaplan, and Goodman-Strauss's paper showing an einstein - a simply-connected polygon - that must aperiodically tile the ...
Mark S's user avatar
  • 2,143
5 votes
2 answers
260 views

Chromatic index of an acyclic digraph

Let $G=(V, E)$ be an acyclic digraph (DAG) with all in- and out-degrees at most $k$. Is it true that the edges of $G$ may be always colored properly in $2k$ colors? In the discussion of this question ...
Fedor Petrov's user avatar
0 votes
0 answers
54 views

Maximum number of h-dimensional hyper-edges without forming any (h+1) complete subgraph

This is about graph theory. Define an h-dimensional hyperedge as a set that contains h vertices. A graph of (h+1) vertices is h-complete if any h combination (or any subset with size h) is an h-...
TanG's user avatar
  • 23
1 vote
0 answers
60 views

Lower bound for the minimum of the maximum frequency of an element - with restrictions

Consider a family $\mathcal{F}$ of non-empty sets, with $n=|\mathcal{F}|$ sets, $q=\left|\cup\mathcal{F}\right|$ elements in the universe, and $q\le n/4$. It is known that of the $\binom{n}{2}$ ways ...
Fabius Wiesner's user avatar
1 vote
1 answer
73 views

Improving a lower bound for the minimum of the maximum frequency of an element in a family of sets

[Originally posted at math.stackexchange without answer] Consider a family $\mathcal{F}$ of $n=|\mathcal{F}|$ sets, $\emptyset \not\in \mathcal{F}$ and an universe $U(\mathcal{F})$ of $q=|U(\mathcal{F}...
Fabius Wiesner's user avatar
3 votes
1 answer
145 views

For every partition of $E(K_{n,n})$ into $n$ colour classes of size $n$, there is a vertex incident to at least $\sqrt{n}$ colours

Given a partition of the edges of $K_{n,n}$ into $n$ colours, where each colour appears exactly $n$ times, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.
Marina Drygala's user avatar
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
1 vote
0 answers
53 views

Chromatic number of 2-graph vs hypergraph of point-line incidences

Define the chromatic number $\chi(H)$ of a (hyper)graph $H$ as the smallest $k$ such that its vertices can be $k$-colored such that no (hyper)edge is monochromatic. Given a finite set of points $P$ in ...
domotorp's user avatar
  • 18.3k
1 vote
0 answers
57 views

Complexity of EFL coloring of a set of lines

Let $M$ be a set of straight lines. Define an EFL coloring of $M$ with $k$ colors as a function $f : P(M) \rightarrow \{ 1,2,\dots,k \}$, such that if two intersection points $p_1, p_2$ belong to the ...
Valentin Brimkov's user avatar
2 votes
1 answer
103 views

"Combined" chromatic number of $2$ graphs glued together with $2$ edges per vertex

If $X$ is any set, we let $[X]^2:=\big\{\{x,y\}:x\neq y\in X\big\}$. If $G=(V,E)$ is an undirected graph and $v\in V$, we define $N_G(v) = \{w\in V:\{v,w\}\in E\}$. For $i =1,2$, let $G_i=(V_i,E_i)$ ...
Dominic van der Zypen's user avatar
1 vote
1 answer
158 views

Graphs with $n$ vertices and $m$ edges and more probable property

Following to my previous question on the same topic, I would like to have some opinions whether the present refinement have some chances to work or is doomed to fail. Given the positive integers $n$ ...
Fabius Wiesner's user avatar

1
2 3 4 5
13