Questions tagged [graph-colorings]
Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.
-3
votes
1answer
80 views
Maximum chromatic number of a $k$-regular graph [on hold]
Let $c_k$ be the maximum chromatic number that a $k$-regular graph can have. What is $\lim\sup_{k\to\infty}\frac{c_k}{k}$?
-1
votes
1answer
65 views
$2n$-regular graphs with maximal chromatic number
Let $n\geq 1$ be an integer. Suppose $m\geq 2n+1$ is an integer. We construct the graph $\mathbb{Z}_m = (\mathbb{Z}/m\mathbb{Z}, E_m)$ where $$E_m=\big\{\{x,y\}:x, y \in \mathbb{Z}/m\mathbb{Z} \text{ ...
2
votes
0answers
51 views
Total Coloring Conjecture for Cayley Graphs
The total Coloring Conjecture(TCC) states that any total coloring of a simple graph $G(V,E)$ has its total chromatic number bounded as $\chi^{T}(G)\le \Delta+2$ where $\Delta $ is the maximal degree ...
3
votes
1answer
67 views
Generalized digraph homomorphisms and graph cores
Given any digraphs $G$ and $H$ we say a surjection $f:V(G)\to V(H)$ reduces $G$ to $H$ if and only if it satisfies $(u,v)\in E(G)\iff (f(u),f(v))\in E(H)$. Where if there exists at least one ...
1
vote
1answer
98 views
On a theorem of Chetwynd and Hilton in Graphs
Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
0
votes
1answer
84 views
Chromatic Polynomials of Circulant Graph With Two Parameters
I have been working with the chromatic polynomials of circulant graphs of prime order $p$ with two distinct parameters, i.e.
$P_{p,i,j}(x):= P(C_{p}(i,j),x)$ with $1 \leq i \neq j \leq \ n/2.$
In ...
3
votes
1answer
63 views
Optimal Strategies for a “Blind” Graph Coloring Game
By the "blind" graph coloring game I denote the following problem, which is played by two players:
player A has $k<n$ colors at hand to color the $n$ vertices of a graph $G$, but that player has ...
4
votes
1answer
74 views
Minimum number of vertices in a $k$-chromatic graph of odd girth $g$
The odd girth of a graph $G$ is defined as the minimum length of an odd cycle in $G$. Let $n_g(k)$ denote the minimum number of vertices in a $k$-chromatic graph of odd girth $g$. What are the known ...
8
votes
0answers
119 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 ...
5
votes
0answers
67 views
Extending colouring of graphs using small number of colours
Conjecture (Csóka-Lippner-Pikhurko). If $G$ is a graph with each vertex of degree $\le d$ with at most $d-1$ pendant edges properly coloured, then this pre-colouring can be extended to all edges of $G$...
4
votes
1answer
208 views
Understanding proof about chromatic number
Consider an undirected graph $K(n,k,i)$, with the all $k$-element subsets of $\{1,\dots,n\}$ as vertices, and two vertices connected by an edge if their sets intersect in less than $i$ elements.
...
-1
votes
1answer
37 views
pruning a special graph
You are given a very special graph. The vertices of the graph come in three
columns: left, center, and right. The edges connect vertices from the left to
vertices in the center, and from the center to ...
8
votes
0answers
349 views
Colored weighted Graphs with only monochromatic perfect matchings
The following purely graph-theoretic question is motivated by quantum mechanics.
Definitions: A bi-colored weighted graph $G(V,E)$ is an undirected graph where every edge is colored, and has a ...
3
votes
1answer
74 views
Maximal matchings in connected graphs
Let $n\in\mathbb{N}$ be a positive integer. Is there a connected graph $G$ such that $G$ cannot be coloured with less than $n$ colours, and every two maximal matchings have non-empty intersection?
(I ...
2
votes
2answers
102 views
Graphs in which all maximal matchings intersect
Let $G=(V,E)$ be a simple, undirected graph. A matching is a set $M\subseteq E$ consisting of pairwise disjoint edges. We say $M$ is maximal if it is maximal amongst all matchings in $G$ with respect ...
4
votes
0answers
133 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. ...
2
votes
0answers
67 views
Tutte polynomial from independent sets of a graph
Let $G$ be a connected graph with chromatic polynomial $X(G,q)$. Since $k$-proper coloring a graph is same as partitioning the vertex set $V$ into $k$ independent sets (a subset of the vertex set in ...
5
votes
1answer
330 views
Countable version of Erdös-Lovasz-Faber conjecture
Let $X$ be an infinite set, and let $(A_n)_{n\in\omega}$ be a collection of subsets of $X$ with the following properties:
$|A_m\cap A_n| \leq 1$ for $m\neq n\in \omega$, and
$|A_n|=\aleph_0$ for all $...
4
votes
1answer
109 views
Increasing the chromatic number by “folding” two vertices of distance 2
Is there a finite, connected, simple, undirected graph $G=(V,E)$ such that
$G$ is not complete, and
whenever two vertices of distance $2$ are identified ("folded"), then the chromatic number ...
1
vote
1answer
42 views
Optimal Graph Splitting
Question:
Given a finite symmetric TSP instance with $2n$ sites, what is the complexity of and what are algorithms for determining two sets of sites $A$ and $B$, each containing $n$ elemenents so that ...
0
votes
0answers
14 views
Name for Spanning Trees Containing all Edges of a Minimum Weight Perfect Matching
This question is motivated by the task of "uniformly" bicoloring the vertices of a symmetric TSP-instance graph with $2n$ vertices.
A simple heuristical requirement for such a bicoloring could be ...
3
votes
0answers
103 views
Hadwiger number of Erdös-Faber-Lovasz graphs
For any set $X$, let $[X]^2 = \big\{\{a,b\}:a,b \in X, a\neq b\big\}$.
We call a finite, simple, undirected graph $G=(V,E)$ an $n$-Erdös-Faber-Lovasz (EFL-) graph if there are $n$ subsets $S_1,\...
5
votes
1answer
69 views
Discrete Hadwiger–Nelson problem variant
The Hadwiger–Nelson problem asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color.
We could build the following ...
15
votes
1answer
277 views
Chromatic numbers of infinite abelian Cayley graphs
The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...
0
votes
0answers
43 views
Edge coloring, with a special condition
I have a problem I am working on that can be reduced to the following case of edge coloring with a special condition.
Let $G$ be a directed graph with infinite vertices that are colored with $m$ ...
0
votes
0answers
28 views
Algorithms for Balanced Coloring of Complete Symmetric Graphs
Question:
Has this the following problem already been studied:
given a complete, weighted, finite symmetric Graph $G$ with $kn$ vertices, assign to each of the vertices one color from $k$...
3
votes
0answers
66 views
chromatic number of plane using Cairo pentagonal tiling
Scale the Cairo pentagonal tiling so the short side is of length 1. Then it is easy to colour the tiling with 8 colours, two parallel ribbons of four colours each, to establish that the chromatic ...
1
vote
3answers
327 views
how to get the coefficient of a special term in the expansion of the graph polynomial?
What is the coefficient $c$ of the term $x_1^2x_2^2x_3^2\cdots x_{12}^2$ in the expansion of the following multivariable polynomial:
$(x_1-x_2)(x_1-x_3)(x_1-x_4)(x_1-x_{10})(x_2-x_3)(x_2-x_5)(x_2-...
8
votes
1answer
383 views
Graphs with only disjoint perfect matchings, with coloring
The following purely graph-theoretic question is motivated by quantum mechanics.
Definitions: A bi-colored graph $G$ is an undirected graph where every edge is colored. An edge can either be ...
6
votes
0answers
93 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 ...
3
votes
0answers
108 views
Constructing Graph V from De Grey´s Minimum Bound For the Chromatic Number of a Plane
Background information:
In section 4.2, paragraph 2 of De Grey´s recently published paper (De Grey's Paper pdf), he constructs a graph V, which is used to construct the graphs W, M, and eventually ...
4
votes
1answer
93 views
Size of triangle free graph with chromatic number $n$
What's the largest constant $c >1$ such that all triangle free graphs with chromatic number $n$ has atleast $\Theta(c^n) $ vertices?
2
votes
2answers
260 views
How to label a tree with minimum cost?
Let $T = (V, E)$ be a tree. Let $\Sigma$ be a finite set of labels. Given a label function $\ell : V \to \Sigma$, the cost of $\ell$ is given by
$$\mu(\ell) = \left| \{(u,v) \in E \mid \ell(u) \neq \...
21
votes
0answers
536 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, ...
4
votes
1answer
141 views
Does the existence of a unique chromatic (possibly transfinite) number for every (possibly non-finite) simple graph imply the axiom of choice?
Assuming the axiom of choice I can write for any cardinal number $\kappa$ and any simple graph $G$ that a function $f$ is a $\kappa\text{-coloring}$ of $G$ if and only if the cardinality of the image ...
1
vote
1answer
57 views
Strong and weak chromatic number of infinite bounded hypergraphs
This is a follow-up of an older question.
Let $H = (V, E)$ be a hypergraph such that every member of $E$ has more than $1$ element. Let $\kappa$ be a cardinal. We say that $c: V\to \kappa$ is a weak ...
1
vote
0answers
83 views
Does anybody know how to prove or disprove the following guess about edge coloring of Hypergraphs?
Definition. Suppose $H=(V,E)$ is a hypergraph. Call a hyperedge $e=\{v_1,v_2,\dotsc,v_k\}$ a $k$-star if in the 1-skeleton of $H$ there is a copy of $K^{1,k-1}$ whose union equals $e$. (Obviously in ...
1
vote
1answer
60 views
Strong and weak chromatic number of infinite hypergraphs of finite rank
Let $H = (V, E)$ be a hypergraph such that every member of $E$ has more than $1$ element. Let $\kappa$ be a cardinal. We say that $c: V\to \kappa$ is a weak coloring if for all $e \in E$ the ...
0
votes
2answers
99 views
coloring infinite vertex transitive graph without large cliques
Let $G$ be an infinite vertex-transitive graph (this means that for every $u,w \in V(G)$ there exists an automorphism $\tau$ of $G$ such that $\tau(u) = v$).
We assume that $G$ is undirected, and does ...
0
votes
2answers
292 views
Non-isomorphic graphs with diameter two [closed]
Let $n>1$ be an integer and $[n] = \{1,\ldots,n\}$. What is an example of non-isomorphic simple, undirected graphs $G_i = ([n], E_i)$ for $i=1,2$ with the following properties?
both $G_1$ and $G_2$...
2
votes
1answer
40 views
Is the difference sequence of the maximum size of $k$-colorable subgraph non-increasing?
Given a simple graph $G=(V,E)$, we use $A_k$ to denote the vertex set of a maximum $k$-colorable subgraph in $G$ when $k\ge 1$, and $A_0=0$.
Will the sequence $|A_1|-|A_0|,|A_2|-|A_1|,\cdots,|A_{\...
1
vote
0answers
104 views
Continuous functions “sharing” a point
Let $(X,\tau)$ be a topological space. By $\text{End}(X)$ we denote the collection of all continuous functions $f:X\to X$. We say $f,g\in \text{End}(X)$ share a point if there is $x\in X$ such that $f(...
3
votes
1answer
215 views
Smallest triangle-free graph with chromatic number 5
The Grötzsch graph is triangle-free and has chromatic number 4. At 11 vertices it is the (unique) smallest graph with these properties.
What is the smallest number of vertices needed for a triangle-...
2
votes
1answer
68 views
Hadwiger critical graphs of arbitrarily high chromatic number
This is an update to an older question admitting a trivial example to answer it.
Suppose $G$ is a finite simple graph. Let $h(G)$ denote the Hadwiger number of $G$; that is, the maximum $n\in\mathbb{...
1
vote
1answer
80 views
Sum-coloring a tournament
If $G=(V,E)$ is a loopless finite directed graph and $v\in V$, we set $\text{In}(v) = \{(w,v): w\in V \land (w,v) \in E\}$.
Let $T=(V,E)$ be a tournament such that for every $v\in V$ the set $\text{...
1
vote
1answer
154 views
Some question about a new type of graphs
Let $G$ be a simple graph such that some of its vertices are like a fork. i.e. there is vertices $w,x,a,v$ such that edges $[v,w]$ and $[w,a]$ are incident in $w$ and edges $[w,a]$ and $[x,w]$ are ...
4
votes
0answers
193 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}$ ...
2
votes
0answers
106 views
graph coloring conjecture
Motivation: if smallest planar graph $G=(v,e)$ exist with $\chi(G)$ = 5, then $\delta(G) > 4$ and $\omega(G)< 4$, $e = 3v - 6$ . It's well known no such graph available. Could it be generalized? ...
1
vote
0answers
78 views
Partition of sets of monomials
Given a degree $d>0$ and $x_1,\dots,x_n$, consider the set $S$ of monomials
\begin{equation*}
x_1^{i_1} \cdots x_n^{i_n}
\end{equation*}
with $0\leq i_j\leq d$ for $1\leq j\leq n$ (the exponents ...
-5
votes
1answer
75 views
Graphs where every vertex can be its own color class
Let $G=(V,E)$ be a finite, simple, undirected graph. We say $G$ has the singleton coloring class property (SCCP) if for all $v_0\in V$ there is a vertex coloring $c:V\to\{1,\ldots,\chi(G)\}$ such ...
