Stack Exchange Network

Stack Exchange network consists of 175 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.

1
vote
1answer
31 views

$G$ is obtained from the complete graph $K_n$ by deleting any one edge. Prove that $χ(G) =n−1$

Let $G$ be a graph obtained from the complete graph $K_n$ by deleting any one edge.Prove that $χ(G) =n−1$ My work: $C=\{1,2,3,4.....n\}$ be a set of $n$ colors. Suppose that the edge removed was $e=(...
1
vote
1answer
18 views

Proving two graphs have the same chromatic number

Let $G= (V,E)$ be a graph, and let $G'= (V',E')$ be a copy of $G$. That is, for each $v ∈ V$ there is a corresponding $v' ∈ V'$ and for each edge $(u,v)∈E$ there is a corresponding edge $(u'...
-1
votes
0answers
14 views

Color class and maximum independence set

It is true that very graph G contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set Let G is a graph such that $C_1, C_2, ........
23
votes
1answer
1k views

How to colour the US map with Yellow, Green, Red and Blue to minimize the number of states with the colour of Green

I want to colour the US (only the states) map with Yellow, Green, Red and Blue. I was wondering what would be the lowest number of states with the colour of Green. We can of course use the other ...
0
votes
1answer
21 views

Understanding connection between independent set and chromatic number

I have came across following facts / definitions: Maximum independent set: Independent set of largest possible size. Maximal independent set: Independent set such that adding any other vertex ...
1
vote
0answers
27 views

Using extremal graph theory theorem to prove a theorem in planar graphs

We have, by one of Turán's theorem, that among the $n$-vertex simple graphs with no $r+1$ clique, the complete $r$-partite graph which has its number of vertices in each partite sets differing by at ...
1
vote
1answer
56 views

Prove that chromatic number $\geq \frac{V^2}{V^2-2E}$ [duplicate]

Let us have a simple graph G. (That means no loops and no multiple edges) Prove that $\chi \geq \frac{V^2}{V^2-2E}$ I found the task in the book by John Bondy "Graph Theory with Applications" (Task ...
0
votes
1answer
38 views

Showing that $n \leq \chi(G)\chi(G')$ and $\chi(G') + \chi(G) \geq 2\sqrt n$. [duplicate]

Let $n$ be the number of vertices of $G$. Recall that $G'$ denotes the complement of $G$. Show that a) $n \leq \chi(G)\chi(G')$ and therefore, b) $\chi(G') + \chi(G) \geq 2\sqrt n$. This question ...
5
votes
1answer
51 views

Assign a list L(x) of size two to every vertex x of an odd cycle. Show that there is an L-coloring unless all sets L(x) are the same.

The problem above is from a midterm that I just took in my graph theory class and I didn't know how to answer it. I was hoping to get some tips to better understand the problem and write it out. Thank ...
0
votes
2answers
45 views

A plane graph $G$ is $2-$face colorable if and only if $G$ is eulerian - counter example

Actually, proof is asked in here: Planar graph has an euler cycle iff its faces can be colored with 2 colors. But my question is not about proof but about why is the following graph not a counter ...
2
votes
1answer
39 views

Combinatorics: Existence of a Latin Square

Let $k_n$ be the smallest number such that given an n by n grid with $k_n$ arbitrary numbers in the top left corner and n arbitrary numbers in every other cell, a number can be chosen from each cell ...
0
votes
0answers
27 views

How can I prove that this two statements are equivalent?

Given: complete graph G and I a list assignment for G prove: G has proper coloring $\Leftrightarrow $ $ \forall \;Z\subseteq V(G)$ : $\mid Z \mid \leq \mid \cup_{z\in Z}\; I(z) \mid $ Can someone ...
0
votes
1answer
46 views

Adapt the proof of Vizing’s theorem to obtain a polynomial time algorithm to properly edge colour a graph G with $\Delta(G) + 1$ colours.

Vizing's theorem: Every simple non-directed graph is $(\Delta(G) + 1)$-edge-colorable. The proof in the question is by induction on the number of vertex n. For n = 1, the statement is trivial. For n >...
-2
votes
0answers
23 views

Show that the Ramsey number of $(2K_3,2K_3)$ is 10 [duplicate]

The hint says one can assume $K_{10}$ does not contain a monochromatic $2K_3$, then consider $K_{10} - H$ where $H$ is a bow tie graph and the result graph will be $K_5$...
-1
votes
0answers
51 views

How can I form in python this matrix to the corresponding graph?

im working in graph theory and sagemath or python. for prove that $R(3,3)=6$ is necessary to find a counterexample of a graph where it has neither a triangle monochromatic red nor a $K_3$ blue, for ...
3
votes
1answer
33 views

Vertex order for Greed coloring of a Graph

I'm interested in coloring the graph $G$ with the greedy algorithm. Now I know that the result can depend on the vertex order and can also be very bad. Now I want to show that there is a vertex order ...
0
votes
1answer
27 views

3-edge colorability of planar, triangle-free graphs of maximum degree 3

I know it will have a 4-edge coloring, from Vizing's theorem. I was able to 3-colour every example I tried to come up with. A preliminary search didn't help me find any results either. Grotzsch's ...
1
vote
1answer
43 views

Using the reduction of 3-SAT to 3-COLOR, explain why complexity proofs by reduction work.

I'm reading about the proof that 3-COLOR is in NP-Hard, by reduction of 3-SAT to 3-COLOR (as listed here for example: http://cs.bme.hu/thalg/3sat-to-3col.pdf). And here's a passage from Wikipedia, ...
2
votes
1answer
84 views

color each point in the plane red or blue

Is it possible to color each point of the plane red or blue so that no square with unit side length and monochromatic vertices is formed? EDIT: I think this is possible,for each point in the plane ...
1
vote
0answers
30 views

Proof that the chromatic polynomial of a simple graph G with n vertices has degree n. [duplicate]

I'm very confused as to why the degree of any chromatic polynomial of a simple graph $G$ that has $n$ vertices is $n$. I've tried using strong induction on the number of edges, but I end up getting ...
1
vote
1answer
59 views

Chromatic polynomial of a simple disconnected graph

I'm working in the following graph theroy/coloring excercise: Prove that, if $G$ is a disconnected simple graph, then its chromatic polynomial $P_c(k)$ is the product of the chromatic polynomials ...
2
votes
1answer
19 views

Find the chromatic polynomials of $K_{2,5}$

I'm working in the following graph theory excercise: Find the chromatic polynomials of $K_{2,5}$ Starting from this generalization: I have two cases: Case 1: $x_1$ and $x_2$ are colored ...
1
vote
0answers
10 views

Calculate RGB color values given amounts of two types of melanin

I've been trying to create a function that can take values representing amounts of eumelanin and pheomelanin and return reasonably accurate numbers for red, green, and blue that I can use to tint a ...
3
votes
2answers
43 views

Construct a set of points having some properties (colouring related)

Construct a finite set of points $S$, all in the same plane, such that: Every line in the plane intersects $S$ in no more than $4$ points. If the points of $S$ are arbitrarily coloured ...
1
vote
1answer
26 views

How to morph a 2d grid of saturation and luminance onto the surface of a torus?

For any given hue, we get a Cartesian grid of saturation and luminance like so: I would like to warp this surface to the shape of a torus: such that all the colors are continuous, and that there is ...
1
vote
0answers
28 views

In the complete graph with n vertices, all edges are colored in three colors.

In the complete graph with $n$ vertices, all edges are colored in three colors. Prove that exists a monochromatic connected subgraph with at least $\frac{n}{2}$ vertices. I got this task in math ...
3
votes
2answers
31 views

Possible ways to color vertices

Considering a graph formed by $4$ verticles connected between them (like it's a circle). Having available $3$ distinct colors, in how many ways is it possible to color the verticles of the graph ...
2
votes
0answers
19 views

Optimal improper vertex-coloring of graph with weighted edges

I have an undirected graph with weighted edges. I want to color the vertices with a given $k$ colors. Let's assume there is no proper coloring with $k$ colors such that adjacent nodes will always have ...
0
votes
2answers
77 views

Proving that $\chi(G)=\omega(G)$ if the complement of G is bipartite.

***Please note I am aware that this question was already asked here: Proving that $ \chi(G) = \omega(G) $ if $ \bar{G} $ is bipartite. however, I have a reason to believe the answer given in that ...
1
vote
2answers
35 views

Complete graph with x vertices on a circle has as many edges of neighboring points as the others. Value of x? [closed]

I tried solving this question but cant find any approach to solve it. We are given an integer $x \ge 2$ and a circle. We need to take $x$ different points on the circle and after that draw line ...
1
vote
1answer
23 views

A proper Vertex, Edge, and Face coloring of a surface Graph

Recently in my graph theory class my professor brought up the concept of Total Coloring. I was wondering have there been any theorems/work done on the concept of a coloring of edges, vertices, and ...
5
votes
1answer
69 views

Transient random walk on 3-color 3-regular tree

Suppose that $T=(V,E)$ is a 3-regular tree with root $0$. Suppose that $0$ is colored green. All other vertices are colored blue, red or green, such that each vertex has exactly one neighbour of each ...
5
votes
1answer
117 views

tiles covering a $7\times 7$ square

A $7 \times 7$ board is divided into $49$ unit squares. Tiles, like the one shown below, are placed onto this board. The tiles can be rotated and each tile neatly covers two squares. Note that each ...
0
votes
1answer
120 views

Graph colouring problem

I have the question as stated: For a graph G with n vertices and 4n edges, Alice claims to have a proper colouring with 3 colours.Bob decides to try to find one by testing each of the possible ways ...
0
votes
0answers
49 views

Change of Color in a Graph

Let G be a planar graph with edges colored red and blue. Show that there is a vertex $x$ such that going around the edges incident to $x$ in clockwise order we encounter no more than two changes of ...
0
votes
0answers
14 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
29 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
36 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
66 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
30 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
23 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
39 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
45 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
28 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
83 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
13 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
54 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 ...