Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [coloring]

For questions concerned with graph colorings.

0
votes
0answers
35 views

question on gluing many 1 x 1 squares to form a rectangle

"You have many 1 x 1 unit squares. You may colour the edges with one of four colours and glue them together along edges of the same colour. Your aim is to get an m x n rectangle. For what value of m ...
0
votes
2answers
34 views

Number of rotation invariant 6-colorings of a cube

Consider a cube colored with six distinct colors on its six faces. How many non-equivalent colorings upto rotations are there? That is, how many ways can we color the cube so that we dont get the same ...
5
votes
1answer
88 views

Coloring grid points with two colors

Let $S$ be a set of finite many grid points (points in the coordinate system with integer coordinates). Is it always possible to color them with two colors, red and blue, such that in each vertical ...
1
vote
1answer
19 views

Prove that the even cycles are 2-list-colorable.

I need to prove the statement in the title. It's very easy to show that with a particular 2-list-assignment, we can have a proper 2-list-coloring (e.g. with a greedy coloring algorithm). I'm just not ...
1
vote
1answer
44 views

A question on the distinguishable colorings of an object in relation to the number of fixed points in a conjugacy class

Note: the first half of this post is just for clarity , I'm sure most of you here can just skip to the part labelled ( my actual question) In class we were shown Burnsides counting theorem which ...
0
votes
1answer
23 views

Coloring binary tree edges with given number of colors

Let's say I have a balanced binary tree which has 37 leaves.I can color the vertices of this tree with 37 colors. $$ 37 * 36^{72} $$ ways. How can I find out coloring edges with 37 colors? Original ...
2
votes
1answer
34 views

Finding the smallest number $n$ such that every two-colouring of the edges of $K_n$ contains a Path on 3 vertices

What is the smallest number $n$ such that every two-colouring of the edges of $K_n$ contains a (not necessarily induced) path on 3 vertices?
3
votes
1answer
54 views

Finding a Graph given a chromatic polynomial

Let $f(k) = k^6 - 6k^5 + 15k^4 - 17k^3 + 7k^2$. Show carefully that there is only one simple graph with chromatic polynomial equal to $f(k)$, and find that graph. Verify that the graph you found does ...
0
votes
1answer
38 views

How to prove that the max edge coloring is 2D - 1 (where D is max vertex degree)?

I have this problem that is giving me fits. This problem seems similar to proving that the max coloring of vertices, where the max vertex degree is D, is D + 1. We cannot have two edges that share ...
1
vote
1answer
14 views

Find two graphs with same order, size and chromatic number, but with different chromatic polynomial

I'll call two graphs chromatically equivalent if they have the same chromatic polynomial. It is easy to show that two chromatically equivalent graphs must have the same order, size and chromatic ...
-1
votes
1answer
34 views

Coloring Red and Blue Problem

We color the integers from 1 to 999 with red and blue, so that each integer is assigned one of the two colors. How many different colorings can we construct with the property that there are more red ...
0
votes
1answer
45 views

Petersen graph edge chromatic number

Hi I keep on getting 3 for the edge chromatic number of the Petersen graph. But the Petersen graph has edge chromatic number of 4 and I don’t know how to do that. Can someone please show this by ...
0
votes
1answer
34 views

Show that the 3-color problem is in P when the input graph is a tree.

This one is from university assignment. I am completely stuck on this one and I searched the internet but couldn't find a explanation. Show that the 3-color problem is in P when the input graph is ...
5
votes
1answer
62 views

$n$ lines in a plane, proper coloring of intersection points with just 3 colors

Draw $n$ lines in a plane so that there are no parallel lines and there are no three lines passing through the same point. Each intersection point is colored red, green or blue. Prove that it is ...
1
vote
0answers
49 views

How to color the verteces of triangles in different colors?

I have a directed graph $G=(V_n, E)$, where $V_n =\{1,2,..., n\}$ is the set of vertices and $E$ is the set of edges. I have found the set of triangles which looks like: ...
0
votes
0answers
23 views

Coloring triangles in a Delaunay triangulation on the surface of a 3d sphere.

Suppose a delaunay triangulation over the surface of a 3d sphere (or generally some 3d surface of something topologically equivalent to the sphere). How many colors do I need to color its triangles so ...
0
votes
0answers
22 views

If $\alpha(G\square K_m)\geq n(G)$, then $G$ is $m$-colorable.

Definitions: $G\square K_m$: The Cartesian Product Graph of an arbitrary graph $G$, and the complete graph on $m$ vertices, $K_m$. $\alpha(G\square K_m)$: The size of a maximum independent set ...
5
votes
1answer
60 views

Edge colourings of an icosahedron

I'm referring to problem A6 of the 2017 Putnam competition -- the question is "How many ways exist to colour the labelled edges of an icosahedron such that every face has two edges of the same colour ...
0
votes
0answers
27 views

A question about graph coloring and partition of graph

I got this question from professor, any hint would be helpful. Let $k$ be a positive integer and let $X,Y$ be a partition of the vertex set of the graph $G$ such that $\chi(G[X])\le k$ and $\chi(G[Y])...
0
votes
1answer
52 views

Coloring of two connected subgraphs

I have a graph made from two subgraphs: complete bi-parted $K_{4,4}$ and two triangles graph . These two subgraphs are connected by two edges. My task is to prove the number of proper 3-colorings for ...
3
votes
2answers
51 views

If a graph has a chromatic number $k$, then for any color there is a vertex of that color that has as neighbors all the other colors

Let $G$ a graph and $k= \chi(G)$. Prove that for all $k$-colorings of $G$ and for all colors $i \in \{1,\ldots,k\} $, there exists $u \in V(G)$ of color $i$ such that for every $j \in \{1,\ldots,k\}$ ...
0
votes
1answer
24 views

Prove that each graph with chromatic number $k$ has a definite induced sub-graph with chromatic number $k$.

A graph with chromatic number k is definite if for each vertex $v$, $ChromaticNumber(G-v) < k$. Prove that each graph with chromatic number $k$ has a definite induced sub-graph with chromatic ...
3
votes
2answers
87 views

Square coloring problem only using 2 colors

"We need to color $4×4$ square using $4$ black color and $12$ white color. Then, how many cases it may be? Flip is prohibited but rotating is ok" I tried case by case (inner square and rest) anf ...
0
votes
0answers
48 views

Coloring of the edge of the 1*3 grid

I am trying to find the number of distinct coloring in the following problem: Consider a 1*3 grid (shown as below) using 10 sticks and 8 balls. Color sticks with $m$ colors. How many ways are there ...
3
votes
0answers
49 views

Pixel coloring problem

We have an images $m$ pixels length and $n$ pixels width. There are at least $k$ pixels with different colors. Image and its reverse, reflect and rotation are considered to be equivalent. Permuting ...
4
votes
1answer
40 views

Color an infinite equilateral grid with seven colors. Can it be possible to prove using Pigeonhole Principle that a monochromatic triangle exists?

I found a problem on Brilliant, and wonder if it has a Pigeonhole solution. You have an infinite lattice of equilateral triangles and you would like to fill each node with one of seven colors. ...
0
votes
0answers
32 views

Hadwiger's conjecture for line graphs

Hadwiger's conjecture asserts that for every graph $G$ and every integer $k\geq 0$, either $G$ is $k$-vertex-colourable or it contains $K_{k+1}$ as a minor. I am trying to prove that Hadwiger's ...
5
votes
2answers
214 views

$3$-colourings of a $3×3$ table with one of $3$ colors up to symmetries

Color each cell of a $3×3$ table with one of $3$ colors. What is the number of ways to do so if adjacent cells have different colors? Of course we consider two paintings the same (equivalent) if ...
1
vote
1answer
50 views

Color the vertices such that no adjacent are the same color

How many ways are there to color the vertices with $n$ colors such that adjacent vertices get different colors? I know this will use Inclusion-Exclusion. Since there are $5$ vertices, the total ...
4
votes
1answer
58 views

What is the graph coloring problem that Paul Erdős offered $25 to solve circa 1979?

I know that what I am asking is not a mathematics question, but a question about a mathematics question, so if it is inappropriate and you're thinking to downvote, I would appreciate a comment first, ...
0
votes
1answer
24 views

Coloring the plane and the space with four and five colors

Here are two problems, each one is an olympiad combinatorics problem with coloring the plane and space. A) The plane is colored with four colors. Prove that it is possible to choose three different ...
0
votes
2answers
34 views

number of combinations colouring 10 eggs with 4 colours if one or 2 colours can be used at the same time

I started to solve this question and realised, that if I just add up all the possibilities, it is going to take a lot of time: Here is the complete question from the textbook: Eggs that are all of ...
1
vote
1answer
33 views

Ordered analogue of the chromatic polynomial

Let $G=(V,E), E\subseteq V^2$ be a finite directed graph. For $n\in\mathbb{N}$, consider $$\chi_{G}^{\leqslant}(n)=\#\Big\{f : V \to \{1, \ldots, n\}\ \Big|\ \big(\forall (u,v)\in E\big)\big(f(u) \...
0
votes
1answer
36 views

Propositional logic implications from a triangle not being 2 colorable

Let S3 = {p1⇔(¬p2), p2⇔(¬p3), p3⇔(¬p1)}. Using that a triangle does not admit a 2-coloring, show that the set S3 is not satisfiable. Let n≥2. Show that the set S(n) defined by S(n) = {p1⇔(¬p2), p2⇔(¬...
0
votes
1answer
183 views

If every subgraph of an undirected graph has at least one vertex with degree at most $k$, then the graph can be colored with at most $k+1$ colors.

I try to prove the following statement: "If every subgraph of an undirected graph has at least one vertex with degree at most $k$, then the graph can be colored with at most $k+1$ colors" My first ...
1
vote
1answer
24 views

Prove The Graph Formed by joining 2 Graphs Colorable in k colors by k-1 Edges is Colorable in k Colors

The crux of the proof for a graph with $\chi(G)=k+1$ being $k-1$ edge connected relies on the construction that demonstrates a graph $G$ formed by the joining of 2 graphs $G_1$ and $G_2$ each ...
1
vote
1answer
39 views

Difference between chromatic number and minimal vertex covering

I have just started learning graph theory not long ago, this is a past year problem and I got the correct answer by chance(True/False questions), wanted to check my understanding on this site. My ...
0
votes
1answer
31 views

In a grid of convex polygons, what is the maximun number of adjacent neighbors a polygon could have?

Maybe is a dumb question, but I'm working in a procedural map generation system. Each map is composed by regions. I know for sure that each polygon is convex, because I'm using a Voronoi space ...
-1
votes
1answer
49 views

Coloring number with this polygon [closed]

I ended up 3 * 2 * 2 * 2 * 2 * 2 = 96. But it was wrong. How can you find out coloring vertices in this polygon?
0
votes
1answer
48 views

Drawing a graph with chromatic polynomial

I have chromatic polynomial, $$P(k) = k^2 (k-1)^2 (k-2).$$ How can I draw a graph with given equation?
2
votes
1answer
50 views

Real roots of Chromatic Polynomial

This question consist of two parts: The first one seems much easier. $1.$ The only real $x<1$ which can be a root of a chromatic polynomial is $0$ $2.$ No real root of a chromatic polynomial can ...
0
votes
1answer
27 views

Understanding Brooks' Theorem from Graphs and Digraphs.

I've been reading up on Brooks' Theorem as stated in Graphs and Digraphs by Chartrand et al. As shown in the above snippet. What has stumped me is the highlighted sentence. Since $H$ is $k$-critical, ...
1
vote
2answers
37 views

Find a decomposition of K2n into two subgraphs G1 and G2 such that χ(G1) + χ(G2) = n+2.

I've found a decomposition for $K_4$ into 2 $P_2$'s and a $C_4$ and several decompositions of $K_6$ and above that fit this property where $\chi(G)$ is the chromatic number of the given graph. How ...
0
votes
3answers
78 views

Four Color Map Theorem Disproof

I don't know if this is considered a valid map... please explain?
2
votes
1answer
138 views

Spiral path on a Penrose tiling

I would like to color a Penrose tiling by following a "spiral path", painting each tile according to a given color sequence. In this picture, I illustrate what I am looking for: The dashed line ...
4
votes
1answer
45 views

Black-White Grid coluring without cycles

(I am assuming this is a known question but can't find the right terminology) Given a $N\times{}N$ grid, colour some of the squares black so that there are no cycles in the "graph". For example, this ...
4
votes
2answers
77 views

Understanding a fact in a proof of Brooks's theorem

In page 90 of Harris, Hirst and Mossinghoff's Combinatorics and Graph Theory, Brooks's theorem is stated as follows: If $G$ is a connected graph that is neither an odd cycle nor a complete graph, ...
4
votes
2answers
128 views

Chromatic number in a union of planar graphs

I am trying to solve the following problem: Let $G_1, G_2, \dots,G_{100}$ be $100$ planar graphs on the same vertex set $V$ , with edge sets $E_1, E_2,...,E_{100}$, respectively, and consider the ...
3
votes
1answer
31 views

Question About Divisors Of Coloring Polygons

I've done a lot of questions about coloring, so I have a question about this. If an $n-$gon's vertices can be colored with $c$ distinct colors with no adjacent vertices being the same in $a$ ways, ...
4
votes
6answers
797 views

Colouring of $\mathbb{N}$ that avoids all non-constant infinite arithmetic progressions?

Can you color every positive integer either black or white such that there are no entirely white or entirely black non-constant infinite arithmetic progressions? How about switching color every power ...