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

1
2 3 4 5
9