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
9 views

MATLAB: color scale with probplot

I have two 1D vectors of the same length, data and my_parameter. I use probplot to see the ...
1
vote
1answer
17 views

Monochromatic loop in plane

Suppose all the points in the plane are coloured with two colours. Are we guaranteed to find a continuous closed monochromatic path in the plane ? I believe the answer is yes, and then what if ...
0
votes
1answer
32 views

Choosing a set of $m$ cards such that they all have distinct values

A deck of $m*n$ cards with $m$ values and $n$ colors is made of one card of each value and color. The cards are arranged in any array with $n$ rows and $m$ columns. Show that we can pick a set of $m$ ...
1
vote
1answer
29 views

Find (if there exists) a graph $G$ such that $X'(G)=5$ and $X(G)=6$. If there is no such a graph then explain why.

Find (if there exists) a graph $G$ such that $X'(G)=5$ and $X(G)=6$. If there is no such a graph then explain why. So we know the following things $[1]$ $X(G) \leq \Delta(G)+1$ or $X(G) \leq \Delta(...
3
votes
1answer
38 views

Assign two colors to nodes in a graph with constraint

Suppose I have a connected graph $G$, where each node has degree at least $d$. Now I want to assign two colors (blue and red) to the nodes. The constraint is that for each node, there should be $k$ (...
4
votes
0answers
58 views

Colouring a sequence

Define a 2 coloring of $\left \{ \left. 0,1 \right \}^* \right.$ to be a function $\chi:\left \{ \left. 0,1 \right \}^* \right. \rightarrow \left \{ \left. red,blue \right \} \right. $ e.g. if $\chi(...
0
votes
1answer
23 views

Edge colouring of regular vertex-transitive graphs

Suppose that $\Gamma = (V\Gamma, E\Gamma)$ is a locally finite simplicial graph, i.e. $V\Gamma$ is a set and the set of edges $E\Gamma \subseteq \binom{V\Gamma}{2}$ consists of unordered tuples of ...
1
vote
1answer
21 views

Coloring and Maximum number of Dominoes

I have joined a course and we are given the following questions, I am still a beginner btw. Find the maximum number of 2×1 dominoes that can be placed on an 8 × 9 chessboard if six of them are placed ...
1
vote
1answer
30 views

Relation between chromatic number and average degree

In my lecture notes, I read that a graph G which has vertices whose average degree is at most $d$ is not $d + 1$ colorable. This seems counter-intuitive to me. I have tried examples with various ...
1
vote
1answer
42 views

Coloring of circle with 12 sections

We have a circle with 12 (equally sized) sections. In how many ways can you color the circle if we consider two results similar if you can get one from the other by rotating the circle? (I'm looking ...
2
votes
1answer
24 views

3-edge colorable cubic graph with an embedding on an orientable surface that is not 4-face colorable

Let $G$ be a simple cubic graph that is cellularly embedded on a surface such that the regions of $G$ are 4-colorable. Then by labeling the colors by the elements of $\mathbb{Z}/2\mathbb{Z} \times \...
1
vote
0answers
37 views

Maximal chromatic polynomial of a graph with fixed chromatic number

Consider all the graphs with $n$ vertices and whose chromatic number is $k$, note that the graph does not have to be connected. What are the graphs with the maximal chromatic polynomial among those ...
7
votes
1answer
75 views

A new graph invariant? The maximum number of non-equivalent colorings with $n$ colors.

Consider (proper) coloring of a finite graph $G$ with exactly $n$ colors and the following coloring transformation: choose an edge of the graph with the end nodes of colors $a$ and $b$ and swap the ...
0
votes
0answers
11 views

Coloring triangular dihedral #2

To start with, my dihedral is a bit specific, here is a picture I need to find amount of ways to color faces ( there are 8 ) into 3 colours. I have already something in my mind because of help ...
1
vote
1answer
46 views

Show that: $\chi(G) + \chi(\overline{G}) \leq |V| + 1$

Show that: $\chi(G) + \chi(\overline{G}) \leq |V| + 1$ I have problem with starting with this task. I have already done similar ones like for example $\chi(G) * \chi(\overline{G}) \geq |V|$, but I ...
4
votes
0answers
51 views

Edge coloring of a graph $G$ with node degrees divisible by $p$ and number of edges NOT divisible by $p$

Given a graph $G=(V,E)$ with node degrees divisible by $p$ and number of edges not divisible by $p$, show that there exists a coloring (using $p$ colors) of the edges such that for every vertex the ...
1
vote
1answer
42 views

Coloring sides of truncated triangular dihedral(bipiramid) into 3 colours

I need to find out the amount of ways to colour truncated triangular dihedron into 3 colours. So, the task will be easier if I had simple triangular dihedron. First of all, do I understand right ...
2
votes
2answers
62 views

4 color theorem equivalent to cubic planar bridgeless are 3 edge colorable

To follow on [How to prove Tait's theorem about planar cubic bridgeless graph being 3-edge-colorable? The four-color theorem is equivalent to the claim that every planar cubic bridgeless graph ...
6
votes
0answers
49 views

A graph-coloring problem where only some of the edges should be bichromatic

In a standard graph-coloring problem, it is required that all edges will be bichromatic (i.e., all edges should be connected to two vertices with different colors). What is a term, and some basic ...
1
vote
0answers
41 views

Monochromatic triangle - graph coloring

I'm trying to find the smallest $n_c$ for which the problem of proving a complete graph with $n$ vertices with edges colored with $c$ colors has a monochromatic triangle could be simplified to a ...
1
vote
1answer
36 views

Minimum number of colors enough to color the vertices of any graph whose vertex lies on at most $k$-odd cycles.

I've got no time to solve this problem during the exam as it's the last one. What is the minimum number of colors that would suffice to color a graph so that adjacent nodes get different colors if ...
1
vote
2answers
36 views

Is right this chromatic polynomial for this Bridge Graph?

I have the following graph: Bridge Graph with N = 8 And I need to find its chromatic polynomial. Based in my notes, I have reached the following result: $$Pg(x) = \frac{((x-1)^4 + (x-1))^2}{x(x-1)...
0
votes
1answer
47 views

Number of ways of coloring n objects which are laid in a row with k colors such that the adjacent objects are of different colors

Given n objects, which are lying in a straight line next to each other, in how many ways we can color them with k colors (all must be painted) such that the adjacent boxes not of same colors. I can ...
2
votes
2answers
71 views

How to prove Tait's theorem about planar cubic bridgeless graph being 3-edge-colorable?

How can be proved, that The four-color theorem is equivalent to the claim that every planar cubic bridgeless graph is 3-edge-colorable. I can't figure out or find any prove of this theorem. ...
3
votes
1answer
54 views

Chromatic number of the pancake graph is subadditive

It turns out that the approach used in Chromatic number of the pancake graph can be generalized and simplified, leading to even better upper bounds. Theorem: For all positive integers $n$ and $m$, we ...
3
votes
0answers
58 views

Chromatic number of the pancake graph

EDIT: This question is superseded by Chromatic number of the pancake graph 2 The pancake graphs are described on https://en.wikipedia.org/wiki/Pancake_graph. The WIKI page gives a rather complicated ...
1
vote
0answers
47 views

How to show that q-coloring graph is ergodic

Informal: I want to show that a q-coloring of graph $G$ is ergodic (i.e. strongly connected and aperiodic) Formally: For a given graph $G(V,E)$ where $|V|=n$ with maximum degree $\Delta\geq1$. Also, ...
0
votes
2answers
40 views

Confusion about a proof on Mycielski construction and chromatic number

Theorem 10.10 of the textbook "A First Course in Graph Theory (2012)" by Gary Chartrand and Ping Zhang is as follows: For every integer $k \ge 3$, there exists a triangle-free graph with chromatic ...
0
votes
0answers
22 views

Relation between deficiency and conformability

Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
0
votes
1answer
28 views

Chromatic polynomial with constant sign on $x > n -1$ and $0<x<1$

Let $G$ be a connected graph with $n$ vertices and chromatic polynomial $p_G(x)$. Prove that: a) $(-1)^{n-1}p_G(x) > 0$ for $0<x<1$. b) $p_G(x)>0$ for $x>n-1$. For a), the case of a ...
2
votes
1answer
32 views

Combinatorics problem (coloring squares)

I'm having some trouble with a combinatorics problem and I was thinking maybe somebody could give me a little help. I've been thinking about it the entire day and I can't get my head around it. It ...
2
votes
0answers
27 views

Chromatic Polynomial of Circulant Graph with Two Parameters

It is easy to get the Chromatic-Polynomial of a Circulant-Graph of size $n$ with one parameter $P[C_{n}(i),x]$. Is there a way to get an explicit formula for the chromatic polynomial of a circulant ...
1
vote
1answer
27 views

Question - Chromatic Polynomial for Given Graph

I am trying to find the chromatic polynomial for the graph below: I am using the inclusion-exclusion principle. Here are my bad cases: $A_1 = \{1 \text{ and } 2 \text{ colored the same }\}$ $A_2 =...
2
votes
1answer
40 views

Optimal Tree Labelling

I am trying to solve the following problem : For a tree $T = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges. A label $L$ of $T$ is an application from $T$ to $\{0,1\}^{|V|}$. ...
0
votes
0answers
43 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
37 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
113 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
21 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
55 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
33 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
40 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
94 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
45 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
18 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
46 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
60 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
41 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
68 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
51 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
25 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 ...