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
2 votes
0 answers
108 views

List total chromatic number of complete graphs

Since for an odd integer $n$, a complete graph on $n$ vertices is list-edge-$n$ choosable, and the total chromatic number is $n$, it is easy to see that the list total chromatic number is bounded ...
vidyarthi's user avatar
  • 2,007
3 votes
1 answer
199 views

Chromatic number of a family of graphs

It is well-known that if a graph has maximum degree $d$, then it is $d+1$ colorable. Say we have $d+1$ graphs $G_1,\ldots, G_{d+1}$ on the same vertex set $V$, and say each $G_i$ has maximum degree at ...
alpmu's user avatar
  • 785
3 votes
1 answer
265 views

Evans conjecture for symmetric latin squares

The Evans conjecture ( which was proved later by Smetaniuk) states that for any $n$, if at most $n-1$ entries of a partial $n\times n$ latin square are filled, it can be completed to the full latin ...
vidyarthi's user avatar
  • 2,007
0 votes
0 answers
113 views

Procedure to color the edges of a circulant graph

From the first theorem in this paper, it is clear that a cayley graph on abelian group for all generating sets of even order is class $1$, that is can be edge colored in exactly $\Delta$ colors. But, ...
vidyarthi's user avatar
  • 2,007
6 votes
1 answer
161 views

Embedding any graph into a vertex-transitive graph of the same chromatic number

If $G=(V,E)$ is a simple, undirected graph, is there a vertex-transitive graph $G_v$ such that $\chi(G) = \chi(G_v)$ and $G$ is isomorphic to an induced subgraph of $G_v$?
Dominic van der Zypen's user avatar
1 vote
0 answers
101 views

Kernel perfect orientations of complete graphs

How can we create a kernel perfect orientation of a complete graph? A kernel of a graph is a set of vertices in a graph $G$, which absorbs other vertices, that is, has all the vertices in its ...
vidyarthi's user avatar
  • 2,007
1 vote
0 answers
112 views

If choosability of complement is known, can the choosability of the graph be known?

Suppose, we know that $G$ is a regular graph of odd order that is $k$- edge choosable, where $k$ is the degree. Then, is it true that $\overline{G}$ has list edge chromatic number at most $n-k+1$? I ...
vidyarthi's user avatar
  • 2,007
2 votes
1 answer
85 views

List coloring of a graph corresponding to a Steiner triple system

Consider the Steiner triple system $S(2,3,n)$ for a suitable integer $n$. We define a graph $G$ with all the vertices as precisely the blocks of the above steiner triple system and any two points ...
vidyarthi's user avatar
  • 2,007
4 votes
1 answer
199 views

Embedding any graph in a regular graph with the same chromatic number

If $G=(V,E)$ is a simple, undirected graph, is there a regular graph $G_R$ such that $G$ is isomorphic to an induced subgraph of $G_R$ and $\chi(G) = \chi(G_R)$?
Dominic van der Zypen's user avatar
6 votes
1 answer
177 views

On a limit involving a transform of the chromatic polynomial

I was playing around with the chromatic polynomial (denoted here by $\chi_G(x)$) and I have made the following conjecture. Let $(G_n)_{n \ge 1}$ be a sequence of graphs with $v(G_n) \to \infty$ ($v(...
mtsecco's user avatar
  • 93
3 votes
1 answer
344 views

Graph which is maximal triangle-free 3-colorable, but not maximal triangle-free

I am looking for a graph which is maximal triangle-free 3-colorable, but not maximal triangle-free. Here a graph which is maximal triangle-free 3-colorable is a graph where the addition of any edge ...
bottledcaps's user avatar
4 votes
1 answer
173 views

Are K_t-minor free graphs on small vertex sets understood?

In a paper on Hadwiger's conjecture, https://web.math.princeton.edu/~pds/papers/hadwiger/paper.pdf, Seymour explains various results on excluding the complete graph as a minor. In particular, there is ...
user62562's user avatar
  • 399
3 votes
1 answer
322 views

Does every maximal almost disjoint family have the same chromatic number?

If $H=(V,E)$ is a hypergraph such that $V\neq\varnothing\neq E$ and $|e| > 1$ for all $e\in E$, and $\kappa\neq\varnothing$ is a cardinal, we say that a map $c:V\to\kappa$ is a coloring if the ...
Dominic van der Zypen's user avatar
1 vote
2 answers
210 views

Hedetniemi for pseudo-chromatic number $\psi(G)$

Let $G=(V,E)$ be a finite simple graph. We say a map $p:V\to [n]:=\{1,\ldots,n\}$ is a pseudo-coloring if for all $a\neq b\in[n]$ there is $v\in\psi^{-1}(\{a\})$ and $w\in\psi^{-1}(\{b\})$ such that $\...
Dominic van der Zypen's user avatar
3 votes
0 answers
142 views

Chromatic number of regular graphs using spectra

There exist inequalities relating the maximum and minimum eigenvalues of the adjacency matrix of a graph with its chromatic numbers, i.e. the Wilf's and Hoffmann's inequalities, which put together ...
vidyarthi's user avatar
  • 2,007
6 votes
1 answer
247 views

List chromatic index of a particular graph

Consider the graph $G$ of order $n$ consisting of two disjoint cliques of even order $\frac{n}{2}=p+1$ (where $p$ is odd prime) joined by a bipartite graph (that is, deleting the edges of the two ...
vidyarthi's user avatar
  • 2,007
0 votes
1 answer
132 views

Decomposition of regular graphs

Let $G$ be a regular simple graph with degree $\Delta=n-k-1$ and order $m$. Let $C_k$ be the regular graph which is formed by removing a $k$-factor from the complete graph $K_{n}$. I think we could ...
vidyarthi's user avatar
  • 2,007
2 votes
2 answers
215 views

The edge precoloring extension problem for complete graphs

Consider coloring the edges of a complete graph on even order. This can be seen as the completion of an order $n$ symmetric Latin square except the leading diagonal. My question pertains to whether we ...
vidyarthi's user avatar
  • 2,007
0 votes
0 answers
113 views

Vertex cover algorithm

Given a graph $G(V, E)$, remove the vertex (or one of the vertices) with the highest cardinality from $G$ and put it in a list $L$. Repeat until in $G$ there are only vertices with cardinality $0$ (no ...
Mario Giambarioli's user avatar
11 votes
1 answer
355 views

Graph chromatic numbers defined by interactive proof

Edit (2020-07-15): Since the discussion below is perhaps a bit long, let me condense my question to the following Short form of the question: Let $G$ be a finite graph (undirected and without self-...
Gro-Tsen's user avatar
  • 29.9k
1 vote
0 answers
132 views

The chromatic polynomial of a line graph

Is there a way to obtain the chromatic polynomial of the line graph of a regular simple graph, having known the chromatic polynomial of the graph? There already exist characterizations of line graph ...
vidyarthi's user avatar
  • 2,007
2 votes
1 answer
215 views

Non-conformity colorings

Motivation. Recently I attended a little party (adhering to physical distancing and in accordance to other COVID19-related laws). An attendee told me that he chose drink $Y$ since at least half of his ...
Dominic van der Zypen's user avatar
0 votes
1 answer
173 views

Relationship between cycle length, number of chords, and number of induced $P_{4}$ subgraphs of the cycle

I was wondering if there was a known relationship between the length of cycle, the number of chords of the cycle, and the number of induced $P_{4}$ subgraphs of the cycle. Here, I am referring to ...
yessssir's user avatar
0 votes
1 answer
116 views

Relaxing Meyniel graphs: condition for strongly perfect instead of very strongly perfect

A Meyniel graph, $\mathcal{G}$ is a graph in which every cycle of odd length at least 5 has at least 2 chords. First off, I have a technical question which is very important to me: what is meant by ...
yessssir's user avatar
1 vote
1 answer
121 views

Bound on the chromatic number of square of bipartite graphs

In continuation of the previous question, what is a strict upper bound on the chromatic number of the square of a bipartite graph? I think the chromatic number number of the square of the bipartite ...
vidyarthi's user avatar
  • 2,007
3 votes
1 answer
413 views

Chromatic number of square of a tree

What is an upper bound on the chromatic number of the square of a tree on $n$ vertices? Note that the power of the graph is considered in this sense. If the tree were a path, then it is easy to see ...
vidyarthi's user avatar
  • 2,007
6 votes
1 answer
369 views

Probability in Chromatic number upper bound of induced subgraph

Let $G=(V, E)$ be a graph with chromatic number $\chi(G)=1000 .$ Let $U \subset V$ be a random subset of $V$ chosen uniformly from among all $2^{|V|}$ subsets of $V$. Let $H=G[U]$ be the induced ...
Ever Garden's user avatar
6 votes
2 answers
842 views

3-colored triangulations of the sphere $S^2$, and Sperner's Lemma

I noticed something about colored triangulations of the topological sphere $S^2$ and have a question about this. Observation. If you triangulate the sphere $S^2$ and color the vertices with three ...
Claus's user avatar
  • 6,777
0 votes
1 answer
58 views

Minimal and maximal degrees in critical graphs

Let $G=(V,E)$ be a finite simple undirected graph. We say that $G$ is critical if for all $v\in V$ we have $$\chi(G\setminus\{v\}) < \chi(G).$$ By $\Delta(G)$ and $\delta(G)$ we denote the maximum ...
Dominic van der Zypen's user avatar
4 votes
1 answer
137 views

Chromatic number of regular linear hypergraphs on $\omega$

For any cardinal $\alpha \in \omega\cup \{\omega\}$, let $[\omega]^\alpha$ denote the collection of subsets of $\omega$ having cardinality $\alpha$. A linear hypergraph $H=(V,E)$ is a hypergraph such ...
Dominic van der Zypen's user avatar
3 votes
0 answers
189 views

Clique cover number of a generalized Kneser graph $K(n,4,2)$

Recently I attacked this combinatorial question. The value of $m(n)$ introduced in it equals to a clique cover number of a generalized Kneser graph $KG_{n,4,1}=K(n,4,2)$ (or the chromatic number of ...
Alex Ravsky's user avatar
  • 4,102
2 votes
1 answer
250 views

Independent sets in complement of Kneser graphs

Intuition strongly suggests that there exist $\left\lfloor\frac{\binom{n}{k}}{\lfloor\frac{n}{k}\rfloor}\right\rfloor$ independent sets in the complement of a Kneser graph each having $\lfloor\frac{...
vidyarthi's user avatar
  • 2,007
5 votes
1 answer
394 views

What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?

Also asked on MSE: What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?. Consider the set $X = \{1,2,3,\dots,n\}$. Define the collection of all $4$-subsets of $X$ by $$\mathcal A=...
ArtOfProblemSolving's user avatar
0 votes
0 answers
67 views

Hypergraph coloring in linear hypergraphs

Let $H=(V,E)$ be a hypergraph with $V\neq\varnothing$ and $E \neq \varnothing$ such that for all $e\in E$ we have $|e|\geq 2$, and for all $e\neq e_1 \in E$ we have $|e\cap e_1|\leq 1$. Is there a ...
Dominic van der Zypen's user avatar
3 votes
1 answer
145 views

Structure of boundary labelling in Sperner‘s Lemma

Consider a triangulated polygon in the 2-dimensional plane, where each vertex is labelled green, blue, or orange. Sperner's Lemma asserts that a fully-colored triangle exists in the triangulation, if ...
Claus's user avatar
  • 6,777
3 votes
1 answer
72 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 ...
scubbo's user avatar
  • 131
0 votes
1 answer
131 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 ...
vidyarthi's user avatar
  • 2,007
-1 votes
1 answer
74 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 ...
Dominic van der Zypen's user avatar
3 votes
1 answer
90 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\...
Dominic van der Zypen's user avatar
1 vote
2 answers
94 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 ...
Ruhollah Majdoddin's user avatar
24 votes
1 answer
565 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 ...
Nate's user avatar
  • 1,992
5 votes
1 answer
160 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 ...
Pascal Ochem's user avatar
10 votes
1 answer
210 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 ...
Dexter's user avatar
  • 223
0 votes
0 answers
84 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 ...
prideout's user avatar
  • 173
7 votes
1 answer
1k 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, ...
prideout's user avatar
  • 173
1 vote
0 answers
52 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-...
lchen's user avatar
  • 459
1 vote
0 answers
53 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 ...
RayyyyySun's user avatar
1 vote
1 answer
186 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 ...
Dominic van der Zypen's user avatar
0 votes
1 answer
40 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,\...
Dominic van der Zypen's user avatar
2 votes
1 answer
96 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 ...
Dominic van der Zypen's user avatar

1 2 3
4
5
13