# Questions tagged [coloring]

For questions concerned with graph colorings.

1,415 questions
Filter by
Sorted by
Tagged with
27 views

### Finding sum of all weights with colourings

There are 128 vertices in the graph. Each edge has a weight written on it. You can ask questions to each edge: you can paint the edge in two possible colors to find out the sum of the weights on the ...
31 views

### Brooks' Theorem Time complexity

I am looking to derive an algorithm that finds, for every connected graph $G$ that is neither complete nor an odd cycle, a $\Delta(G)$-colouring in time $O(m+n)$. When we proved Brooks' theorem we ...
43 views

### Find the minimum number of colors to color any Map on Torus.

I am finding the minimum number of colors to color any map on torus. I have drawn how complete graph $K_5$ can be embedded on a torus. I know that the chromatic number of this graph is $5$ and we ...
251 views

### Why do greedy coloring algorithms mess up?

It is a well-known fact that, for a graph, the greedy coloring algorithm does not always return the most optimal coloring. That is, it strongly depends on the ordering of the vertices as they are ...
55 views

1 vote
66 views

### Proof suggestion for "The chromatic number of a $k$-degenerate graph is inferior or equal to $k + 1$"

I have developed a proof by induction but I don't feel confident in its validity: Base case ($n = 1$) If $G$ only contains one vertex, then its degree is $0$, then $k = 0$ and G is $1$-colorable. This ...
1 vote
29 views

### What does it really mean to have the complete graph as a minor?

I was looking at the Hadwiger Conjecture and the four color theorem, and tried to get a better grasp of what it really means to have a complete graph as minor. I wondered whether the following three ...
45 views

### Proving that disconnecting edges of a 3-edge-colorable graph are of the same color

I'm struggling to prove the following: Edges of a connected cubic graph G can be colored with 3 colors in such a way that no adjacent edges are of the same color. 2 edges were removed from the graph ...
79 views

### Colouring 9 vertices on a circle.

Today I've got a combinatorics problem that I've been trying to solve and I think I have found a good algorithm to get. The problem is the following Suppose that there are 9 points in a circle. ...
107 views

### n^2-Grid 3n-Coloring Game: Can we color a n-square grid with 3n colors s. t. we cannot choose n colors to obtain an histogram with $\Omega(n^2)$ area?

The coloring game is a game played between Alice and Bob. There exists a grid of size $n \times n$, where $n$ is a strictly positive integer. Each cell of the grid can be colored with a color that ...
1 vote
41 views

### Difficulty understanding coloring of graph and its complement [closed]

Let G denote a simple graph which is 15-colorable and composed of 2022 vertices, prove that the complement of G is at least 135-colorable. I have looked everywhere for a similar problem and can't find ...
43 views

### The chromatic polynomial $P(G, k)$ of a graph is always $\geq k!$

I was playing around with the chromatic polynomial earlier today, when I stumbled upon the following result: If $G$ has a $k$-coloring, then $P(G, k) \geq k!$ I came up with the following proof, but I ... 41 views

### Reference/source of this theorem

Anyone knows the specific reference of the following result? It seems like a standard result in Hypergraph Colorings, so I suspect that it may have been proven (it could be in Extremal Finite Set ...
26 views

### Chromatic number for one vertex

Chromatic number is 3 for odd cycle and 2 for even cycle. A graph with 1 vertex is a cycle with 1 vertex $C_1$. I believe 1 is a odd number. Therefore, $C_1$ is a odd cycle. Now, I am struggling to ...
1 vote
17 views

### Tiling by S-tetrominos and Z-tetrominos on a lattice polygon $P$

We call an S-tetromino and a Z-tetromino for shapes in the image below: Now assume that a lattice polygon $P$ can be covered exclusively using S-tetrominos. Prove that if we also try to use Z-...
65 views

### Number of ways to color a square graph with diagonal line using principle of Inclusion and Exclusion

How many ways can we color the graph if adjacent vertices receive different colors ? It's easy to see that the answer is $n(n-1)(n-2)^2 = n^4-5n^3+8n^2-4n$, where $n$ is the number of colors (fix a ...
104 views

### Show that the chromatic number of a certain graph is at most $5$

I was studying graph theory and stumbled across the following question: Consider a simple graph $G$ with the following property: any pair of cycles of odd length the graph intersect (namely every pair ...
30 views

### What can we say about the colourings of some subset of vertices of a graph

I will clarify the question by defining some straightforward concepts. Let G = (V, E) be a simple graph with chromatic number $k$. We call a subset $V'\subset V$ fully chromatic if every proper k-...
69 views

### Maximum number of edges on a $3-$colorable graph?

There is some way to upper bound the number of edges on a $3-$colorable graph $G$, supposing that $G$ has $n$ vertices? I've did some research but haven't found anything that could help. Thanks in ...
1 vote
23 views

### assymetric graph coloring formulation

I'm reading this articel which is about formulating VCP to eleminate symmetric solution, they say: And then In order to eliminate some of the symmetrical solutions, they say these two constraint is ...
45 views

### How to construct a graph with six vertices that has the chromatic number 4 (not 3)?

I have a question related to graph theory. First, I want to state that I am not a mathematician or computer scientist, but a psychologist doing research on cognitive processing related to computer ...
46 views

### Smallest $K_k$-free graph with chromatic number $\ge k$

It is well known that a (simple undirected) graph $\mathcal G$ may require $k$ or more colors for a proper vertex coloring (adjacent vertices must have different colors) without containing a $k$-...
23 views

### Prove or disprove that there exists a function f : N → N such that, for every graph G, we have χ(G) ≤ f(ω(G)).

Prove or disprove that there exists a function f : N → N such that, for every graph G, we have χ(G) ≤ f(ω(G)). Here in my question, χ stands for the chromatic number and ω stands for the clique number....
25 views

### Constrained coloring of bigraph nodes

I have a graph $G(U,V,E)$ representing a set of documents ($U$) and queries ($V$). Every document has 1-5 queries it is connected to, and every query has 1-50 documents it is connected to. There are ~...
53 views

### What's the optimal bound of this graph coloring problem?

Let $G$ be a graph with nodes $v_1, ..., v_n$ and a set of edges $E$. We denote $\chi(G)$ the chromatic number of G (smallest number of colors to color the graph such that an edge never connects two ...
70 views

### Why problem of Graph colouring is NP-Hard?

I am studying graph coloring and trying to find why graph coloring is NP-Hard. Please share your thoughts or share any resources related to this.Thank you in Advance.
315 views

### Coloring a Generalized Latin Square

Suppose we have an $n \times n$ array, and there is a decomposition $\mathcal{A}$ of its coordinates $a_{i,j}$ into sets $A_m$ as follows: If $a_{i,j} \in A_m$, then $a_{j,i} \in A_m$. So they're ...
1 vote
43 views

### Colouring 4 sections of a $3 \times 3$ grid with two colours.

Let's say there is a $3 \times 3$ grid of squares. You colour any one of those squares green, then you colour another square that isn't coloured and is neither on the same row nor column as the first ...
48 views

### Isn't chromatic number just the minimum number of independent sets?

Almost everywhere I read it defines chromatic number as the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color. But if adjacent vertices ...
1 vote
38 views

### Number of k-colorable labeled graphs on n vertices [closed]

What's the asymptotic behavior of $f(n, k) =$# of k-colorable graphs on n labeled vertices? (To be clear, we are fine with double-counting isomorphic graphs.) Specifically wondering about the case ...
68 views

### Prove that $\chi(G) \leq n$ just when there is a homomorphism from the graph $G$ to $K_n$ [duplicate]

I would be very grateful for help with this proof: "Prove that $\chi(G) \leq n$ just when there is a homomorphism from the graph $G$ to $K_n$." we know that: $\chi(G)$ ... denotes the ...
18 views

### How are 3D objects / fractals colored?

I've seen many diagrams of 3D objects being colored using a variety of colors - actually, not just 3D objects, but also things like fractals (the Mandelbrot set, etc...). I've tried to look up an ...
53 views

### Show that there exists a $c > 0$ and a $n^*$ such that for $n \geq n^*$, every two coloring of $E(K_n)$ contains $cn^3$ monochromatic triangles.

Show that there exists a $c > 0$ and a $n^*$ such that for $n \geq n^*$, every two coloring of $E(K_n)$ contains $cn^3$ monochromatic triangles. I’m wondering whether this statement could be ...
101 views

### $4$-choosability of $K_{10,10}$

A graph is $k$-choosable if no matter how one assigns a list of $k$ colors to each vertex, the vertices in the graph can be coloured in a way that each vertex receives a colour from its list and any ...
143 views

### Are 4 colors necessary to properly color adjacent countries of congruent shape?

The four color theorem proved that at most 4 colors are necessary to properly color any map (countries sharing a border have different colors). My question is the following: Does there exist a map ...