Questions tagged [coloring]

For questions concerned with graph colorings.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
  • 77
0 votes
1 answer
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 ...
user avatar
3 votes
2 answers
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 ...
user avatar
-1 votes
0 answers
55 views

Necklace combinatorics

Consider a circular necklace with $18$ identical beads. We can rotate the necklace and turn it over. Let $G$ denote the symmetry group. How many rotations does $G$ contain? How many reflections does $...
user avatar
  • 9
0 votes
1 answer
67 views

Colourings with no monochromatic triangle containing a fixed vertex

Let $n$ and $k$ be positive integers and fix a vertex $A$ in the complete graph $K_n$ on $n$ vertices. In how many ways can we colour the edges of $K_n$, each with one out of $k$ colours, so that $A$ ...
user avatar
  • 2,547
0 votes
0 answers
30 views

How to find the number of truly (no simple swapping of colors) distinct vertex colorings of a graph?

I am a layman when it comes to mathematics, computer science and , thus, also graph theory. But for designing a psychological experiment based on simple graphs I need to know how to find the number of ...
user avatar
  • 41
1 vote
1 answer
68 views

is this acceptable for the 4 color theorem? [closed]

I've seen some videos and done some general reading on the 4 color theorem and it's mostly been presented in simple circular like maps or networks, i took a shot at trying to make a map that could be ...
user avatar
  • 23
0 votes
1 answer
58 views

Prove that $\chi(G) \le n$ just when there is a homomorphism from the graph $G$ to $K_n$

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 minimum of colors ...
user avatar
  • 51
1 vote
1 answer
154 views

How many squares of each colour are in a generalized checkerboard $C$-coloured $m \times n$ rectangle?

How many squares of each colour are in a generalized checkerboard $C$-coloured $m \times n$ rectangle? Assume an $m\times n$ rectangle has been been divided into a grid of $mn$ unit squares, and the ...
user avatar
  • 13
1 vote
1 answer
21 views

A problem in graph coloring, inspired by the 4CT

Let $G = (V, E) $ be a simple k-chromatic graph. A coloring of $G$ can be assumed to imply a proper k-coloring on the vertices. We call a set of vertices $V'\subset V$ fully chromatic if for any ...
user avatar
2 votes
1 answer
68 views

Prove that χ(G) ≤ n just when there is a homomorphism from the graph G to Kn [duplicate]

I would be very grateful for help with this proof: "Prove that χ(G) ≤ n just when there is a homomorphism from the graph G to Kn." we know that: χ(G) ... denotes the minimum of colors needed ...
user avatar
  • 51
0 votes
1 answer
47 views

In how many different ways can I draw them?

I have a cube and I draw a vertex, a middle of an edge and a diagonal of a face. In how many different ways can I draw them? Two cubes can look similar after a rotation. I don't know how to start.
user avatar
  • 585
2 votes
1 answer
63 views

Random graph is not r-colorable w.h.p.

I need to prove that for fixed integer $r \geq 3$ and for any constant $c > 2r\ln{r}-\ln{r}$ random graph $G\left(n, \frac{c}{n}\right)$ is not r-colorable with high probability, i.e. $$ P\left(\...
user avatar
  • 43
2 votes
1 answer
66 views

Clique number and chromatic number

It is known that $\chi(G) \geq \omega(G)$. However, graph theorists love to sharpen their bounds. Are there known sufficient conditions to ensure that $ \chi(G) = \omega(G)$, where $\omega(G)$ is the ...
user avatar
4 votes
1 answer
61 views

I have a conjecture regarding vertex coloring

Let $G = (V, E)$ be a graph with chromatic number $n+1$, and let there be some vertex $v* \in V$, so that deleting this vertex results in a graph $G/{v*}$ that has chromatic number n. Now, assign to $...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 11
1 vote
1 answer
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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
  • 121
4 votes
1 answer
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. ...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 21
1 vote
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 571
1 vote
0 answers
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-...
user avatar
  • 4,202
2 votes
1 answer
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 ...
user avatar
3 votes
1 answer
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 ...
user avatar
  • 41
0 votes
0 answers
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-...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
  • 41
0 votes
1 answer
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$-...
user avatar
  • 35.2k
0 votes
0 answers
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....
user avatar
0 votes
0 answers
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 ~...
user avatar
  • 176
4 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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.
user avatar
9 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 2,239
1 vote
0 answers
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 ...
user avatar
  • 27
0 votes
1 answer
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 ...
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
  • 85
2 votes
1 answer
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 ...
user avatar
  • 645
6 votes
1 answer
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 ...
user avatar
  • 2,547
3 votes
1 answer
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 ...
user avatar
10 votes
1 answer
514 views

Why is this proof for the four color theorem considered wrong?

I'd like to think I found a proof for the four color theorem, but I also know that it took far smarter people than me a computer simulation to prove. Still, I don't see why this logic should be flawed....
user avatar
  • 227
1 vote
1 answer
58 views

Ramsey Theory on subsets of $\{1, 2, \dots, n\}$, $k$ colored.

Prove that there exists a $n$ natural for each $k > 0$ natural such that, by coloring all the subsets of $\{1, 2, \dots, n\}$ with $k$ colors, there exist two disjoint subsets among them, $X$ and $...
user avatar
1 vote
0 answers
29 views

Can a graph with circumference $n$ always be $n$-colored? [duplicate]

Say a simple graph $G$, which is not necessarily planar, has a circumference of $n$ (that is to say, there exists a subgraph $C_n$ where $n$ is maximized). Is it sufficient to say that the graph can ...
user avatar
  • 1,137
0 votes
1 answer
87 views

Two coloring a tree

Suppose we color the nodes of a tree $T=(V,E)$ with two colors, red and blue, so that any two adjacent nodes have different colors. Can we claim that If there is an even-length path between two nodes ...
user avatar
  • 1

1
2 3 4 5
29