Questions tagged [graph-colorings]
Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.
443
questions
3
votes
1answer
45 views
For which sets of $(n, m, k)$ does there exist an edge-labelling (using $k$ labels) on $K_n$, such that every single-labelled subgraph is $K_m$?
Or, equivalently - for what sets of $(n, m, k)$ is it possible, for a group* of $n$ people, to arrange $k$ days of "meetings", such that every day the group is split into subgroups of $m$ people, and ...
0
votes
0answers
27 views
Complexity of edge coloring of class 1 graphs
We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it ...
-1
votes
1answer
63 views
Effect of collapsing two vertices of distance $2$
Motivating example. Consider the graph $G=(V,E)$ with $V = \{0,1,2,3\}$ and $E = \big\{\{i,i+1\}: i\in \{0,1,2\}\big\}$. We have $\chi(G) = 2$, but if we collapse $0$ and $3$, we get the complete ...
3
votes
1answer
65 views
The effects of collapsing vs joining non-adjacent vertices on the chromatic number
For any set $X$, let $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$.
Is there a finite, simple, undirected, connected graph $G=(V,E)$ with the following properties?
There is $\{v, w\}\in [V]^2\...
0
votes
0answers
37 views
Antimagic labelings to prove total coloring conjecture
An antimagic labeling of a simple graph with order $n$ and size $m$ is a surjective function from the set of edges to a set of labels (numbers) of size $m$ such that the sum of labels of the edges at ...
1
vote
2answers
87 views
One part of a bipartite graph has max degree 3. Partition the other part to 3 ~equal subsets s.t. just a fraction of first part see all 3 subsets
Let $d \gg 1$. Let $G:=(U, V, E)$ be some bipartite graph such that deg$(u) \le d$ for all $u\in U$ and deg$(v) \le 3$ for all $v \in V$.
Now, is it possible to color vertices in $U$ with 3 colors ...
22
votes
1answer
424 views
Doubly periodic 4 color theorem?
Let $G$ be a graph embedded (without crossings) on a torus $T$. It's fairly well known that this implies the chromatic number of $G$ is at most 7. If I lift $G$ to the universal cover of $T$, we get a ...
5
votes
2answers
100 views
Is the acyclic chromatic number bounded in terms of the book thickness?
ISGCI says that the chromatic number of a graph is upper bounded in terms of the book thickness.
https://www.graphclasses.org/classes/par_32.html
This can be improved by saying that the book ...
10
votes
1answer
153 views
Kneser subgraph with high chromatic number
For positive integers $n\geq 2k$, it is known that the chromatic number of the Kneser graph $K_{n,k}$ is $n-2k+2$. Moreover, the Schrijver graph $S_{n,k}$ (definition in the same link), which is a ...
0
votes
0answers
69 views
Can you color a planar graph given a coloring of its triangulation?
Several proofs of the four color theorem (or failed attempts) start with something like "We need only consider triangulations, because every simple planar graph is contained in a triangulation".
On ...
7
votes
1answer
987 views
Could the 4-color theorem be proven by contracting snarks?
Suppose someone came up with an algorithm that could take any snark and perform edge contraction to result in the Peterson graph. If an inspection of the algorithm reveals that it works as claimed, ...
1
vote
0answers
43 views
Graph coloring to minimize maximum number of colors along paths
Given a graph $G$ and a pair of source-destination nodes $s$ and $t$. Each node in $G$ is to be colored. Let $C_i$ denote the available color set for node $i$. Under a coloring scheme $A$, for any $s-...
1
vote
0answers
41 views
Upperbound on Shannon capacity of graph and strong product of graph
Given a Graph $G = (V=[n],E)$, if a symmetric matrix $B$ fits $G$, it has non-zero diagonal elements and 0 on off-diagonal entries if $\{i,j\}$ are non-edge in $G$.
Let \begin{equation}
R(G) = \min ...
1
vote
1answer
138 views
A converse of the Erdős-De Bruijn Theorem?
For the chromatic number $\chi(G)$ of a simple, undirected graph, there is a "compactness" theorem by Erdős and De Bruijn stating that if an infinite graph $G$ has finite chromatic number, then there ...
1
vote
0answers
163 views
Minimum vertex cover and linear programming
Suppose we have a graph G. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $v_{i}...
0
votes
1answer
32 views
Starting point of roundtrip coloring in connected graphs
This is a subquestion for an older question about a certain kind of greedy coloring.
Let $G = (V,E)$ be a finite, connected, simple, undirected graph. By a roundtrip of $G$ we mean a map $r:\{0,\...
2
votes
1answer
88 views
“Roundtrip”-chromatic number of (connected) graphs
Let $G = (V,E)$ be a finite, connected, simple, undirected graph. By a roundtrip of $G$ we mean a map $r:\{0,\ldots,n\} \to V$ for some $n\in\mathbb{N}$ with the following properties:
$r$ is ...
2
votes
1answer
75 views
A problem about the connectivity of vertices that must have the same color for any proper minimal coloring of a graph
I did not get an answer when asking for help with this question in Math Stack Exchange (here). Anyway, I believe that this forum is more suitable for it.
I'm trying to solve a problem about ...
0
votes
0answers
118 views
What is the number of connected graphs with $n$ vertices of max. degree up to $D$? Leaving $F(x) = x + x^2 + 2x^3 + 6x^4 + 21x^5 + 112x^6 + …$
It is known that F(x) is the generating function of the counting sequence of connected simple graphs with N vertices is given by:
$F(x) = x + x^2 + 2x^3 + 6x^4 + 21x^5 + 112x^6 + 853x^7...$
where ...
2
votes
0answers
41 views
Lower bound for the chromatic number in terms of minimum feedback vertex set
Let $MFVS(G)$ denote the size of minimum feedback vertex set of $G$.
We believe we proved $\chi(G) \ge (|G| - MFVS(\overline{G}))/2$
and this bound is sharp.
Is this known or trivial result?
This ...
1
vote
0answers
47 views
Partitionability and colorability of hypergraphs
Motivation. If $\kappa\neq\emptyset$ is a cardinal, then a simple, undirected graph $G=(V,E)$ is $\kappa$-colorable if and only if there is a partition of $V$ into at most $\kappa$ blocks such that ...
0
votes
0answers
29 views
Tutte 1-factor theorem to prove total chromatic number of complete multipartite graphs
Consider a complete multipartite graph on $n$ vertices having maximum degree $\Delta$. Then, it is known that the total chromatic number of the graph is $\le\Delta+2$. The proof uses the fact that a ...
1
vote
0answers
87 views
Relation between the number of spanning trees and the chromatic number of a graph
The number of spanning trees $\tau(G)$ of a simple graph $G$ is seen to satisfy the deletion-contraction recurrence:
$$\tau(G)=\tau(G-e)+\tau(G.e),$$
where $e$ is an edge of the graph $G$ and $G-e$ ...
2
votes
2answers
112 views
Generalization of independence complex of graphs
Let $G$ be an undirected graph with no multiple edges or loops. Recall that the independece system $\mathcal{I}(G)$ consists of all those subsets $A$ of the vertex set such that the induced subgraph $...
1
vote
1answer
87 views
Cliques in overlap graphs for words
Let $\Sigma$ be a finite alphabet, and consider the free monoid $\Sigma^*$. Given $w, w' \in \Sigma^*$ we say that $w$ overlaps $w'$ if there exist non-empty words $u, v, u'$ such that $w = uv$ and $w'...
9
votes
1answer
207 views
When does a graph have a circular orientation? Or equivalently can anyone help me characterize this particular class of $3$-colorable perfect graphs?
Call an oriented digraph $D=(V,A)$ circular when for all $\small x,y,z\in V$ if $(x,y)\in A$ and $(y,z)\in A$ then $(z,x)\in A$ or equivalently if $D$ is any oriented digraph whose arc set is a ...
1
vote
1answer
58 views
A different version of list coloring
Consider a non-regular bipartite graph $G$ . We consider list edge coloring the edges of the graph by giving lists of cardinality $max(deg(v_i),deg(v_j))+2$ for each edge $e=v_iv_j$ where $deg(v_i)$ ...
2
votes
0answers
48 views
Analog of Reed's conjecture for hypergraph
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 number, $\Delta$ is the maximum degree, and ...
5
votes
0answers
161 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 ...
1
vote
0answers
65 views
Total Coloring of a graph with $\Delta\ge\frac{n}{2}$
Consider an even vertex transitive graph $G$, which is not complete, with order $n$ and degree $k$ greater than or equal to half the order. By Hajnal-Szemeredi theorem, we could partition the ...
3
votes
1answer
86 views
What number of colorings can guarantee that for every k-element subset there exists a coloring assigns different colors for elements from this subset?
Let $M(n, k)$ be a minimal number $m$ such that there exists set $C$ ($|C|=m$) of colorings of n-element set $[n]$ with $k$ colors such that for every $k$-element subset $K$ of $[n]$ there exists ...
3
votes
1answer
63 views
Minimal degree in a critical graph
We say that a finite, simple, undirected graph $G=(V,E)$ is $k$-critical for $k\in\mathbb{N}$ if $\chi(G)=k$ and $\chi(G\setminus \{v\}) = k-1$ for all $v\in V(G)$. Let $\delta(G)$ denote the minimum ...
0
votes
0answers
57 views
The order of minor in the total graph of a graph
Does the total graph of a regular finite graph with maximum degree $\Delta$ have a $K_{\Delta+2}$ minor?
I think no. It has a clique of order $\Delta+1$. But, I dont think that deleting a few edges ...
0
votes
0answers
56 views
Minimal degree difference for $k$-critical graphs on $n$ vertices
For a finite, simple, undirected graph $G=(V,E)$ let $\delta(G)$ and $\Delta(G)$ denote the minimum and maximum degree of $G$, respectively.
Is there a constant $K\in\mathbb{N}$ with the following ...
-1
votes
1answer
77 views
Tuza theorem to prove vizing theorem
The Tuza theorem states that every graph with no cycle congruent to 1 mod $k$ is $k$ colorable. Now, the line graph of any simple graph of maximum degree $d$ is seen to posess the property that it has ...
3
votes
0answers
96 views
Lorentzian (=Minkowskian) Hadwiger-Nelson problem: is the chromatic number finite?
Background: Some years ago, I collected a number of thoughts and partial results (which, based on Soifer's Mathematical coloring book, I believed were new) on the Hadwiger-Nelson problem in a note ...
4
votes
1answer
89 views
Complexity of graph 3 coloring and counting algorithm
3-coloring a graph $G$ is equivalent to partitioning the
vertices of $G$ in three independent sets.
The smallest independent set $A$ is at most $n/3$ where $n$
is the order of $G$.
We have $G \...
1
vote
0answers
75 views
Relation between Betti Numbers and Chromatic Number of a simple graph
Is there a relation between the betti numbers of a graph considered as a simplicial complex and its chromatic number?
Typically the first Betti number is said to be the cyclomatic number of the graph....
12
votes
0answers
124 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 ...
2
votes
1answer
53 views
A simple equality for book embedding of two graphs
A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is ...
3
votes
1answer
181 views
Concentration of monochromatic edges in a graph
Let $G$ be a graph of order $n$ with $m$ edges. Color each vertices uniformly at random with $q$ colors. It is easy to see that expected number of monochromatic edges (edge whose end vertices are of ...
1
vote
0answers
42 views
Coloration of an interval graph with constraints [closed]
Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
3
votes
1answer
136 views
Edge coloring graphs is in P?
It is known that there exist polynomial time algorithm to approximate the Lovasz number or the supremum of Shannon capacity of graphs.
By Vizing's theorem, the graph $G$ has only two chromatic ...
2
votes
1answer
89 views
Perfect graphs condition could be weakened?
The perfect graphs are generally defined as those graphs whose every induced subgraph has its chromatic number equal to its clique number.
Now,are there some examples where the clique number of graph ...
1
vote
0answers
92 views
Chromatic number of certain graphs with high maximum degree
Let $G$ be the graph of even order $n$ and size $\ge\frac{n^2}{4}$ which is a Cayley graph on a nilpotent group but not complete. Can the chromatic number of this graph be determined in polynomial ...
3
votes
1answer
236 views
Combinatorial equation system with exponentially many equations in quadratic many variables
A certain question on graph theory (about the existance of graphs with a certain coloring inherited by perfect matchings) can be translated into the satisfiability problem of a certain set of ...
4
votes
0answers
81 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 ...
2
votes
1answer
186 views
List coloring of tripartite graph [closed]
Let $G$ be a tripartite graph with partite sets $A,B,C$. The graphs $A\cup B$, $B\cup C$ and $C\cup A$ are each bipartite. Let the maximum degree of the graph be $\Delta$.
Now, we know that the ...
0
votes
1answer
75 views
If the core of a graph is a forest, then it is Class 1
It is a standard result, due to Fournier, that if the core of a graph (the induced graph by the vertices having their degrees equal to maximum degree of the graph) is a forest (acyclic), then the ...
4
votes
0answers
28 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,...
