Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...