# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
65 views

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

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
112 views

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