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
1
vote
1
answer
115
views
Chromatic number of the insert-and-shift graph on $S_n$
Let $S_n$ be the collection of bijections $\varphi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. In an earlier question, the insert-and-shift graph structure was introduced on $S_n$ and the resulting graph is ...
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 ...
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) \...
5
votes
1
answer
188
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]^...
3
votes
1
answer
109
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 ...
1
vote
1
answer
103
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 ...
2
votes
2
answers
73
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 ...
2
votes
1
answer
95
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 ...
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) ...
0
votes
0
answers
39
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 ...
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 ...
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 ...
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....
1
vote
1
answer
197
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 ...
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 ...
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 ...
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 ...
3
votes
1
answer
227
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 ...
2
votes
1
answer
125
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 ...
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 ...
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\...
2
votes
1
answer
86
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 ...
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 ${\...
1
vote
2
answers
125
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$-...
3
votes
1
answer
121
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 ...
0
votes
3
answers
124
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 ...
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 ...
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:...
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 ...
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$.
...
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 ...
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?
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-...
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 ...
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 ...
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.
...
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 ...
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),\\...
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 ...
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 ...
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 ...
5
votes
2
answers
263
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 ...
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-...
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 ...
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}...
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.
9
votes
0
answers
309
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 ...
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 ...
7
votes
1
answer
365
views
What is this Ramsey problem?
Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ ...
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 ...