For questions concerned with graph colorings.

learn more… | top users | synonyms (1)

2
votes
1answer
39 views

Finite coloring of an interval

Two real functions, $f$ and $g$, are defined on the interval $[-1,1]$. Each point $x$ in the interval is colored in one of 3 colors: Red - if $f(x)>g(x)$ Blue - if $f(x)=g(x)$ Green - if ...
0
votes
0answers
30 views

Coloring a circle

A circular spintop is colored in blue, red and green. Whenever the spintop is rotated 120 degrees, the pattern of colors looks exactly the same, only that blue becomes red, red becomes green and green ...
1
vote
1answer
24 views

calculating a chromatic polynomial

I am going through some questions in the "Bondy,Murty - Graph Theory with applications" book, and I have stumbled upon the following question: calculate the Chromatic Polynomial of the following ...
2
votes
1answer
41 views

How many different cubes can be obtained if four colours are used?

I would like a confirmation to my answer. In this question, faces sharing a common edge cannot be of the same colour. My way of reasoning started by choosing the colours Red (R), Yellow (Y), Green ...
2
votes
2answers
50 views

Graph Theory triangle (3 colors) [duplicate]

Show that if the edges of $K_n$ are colored with $n$ different colors, then there must be a triangle where all three edges have distinct colors. So, I want to use induction on $n$ where $n$ is the ...
1
vote
1answer
13 views

Proper $n$-coloring of a graph clarification

There exists a theorem that states: Let G be a planar graph. There exists a proper 6-coloring of G. Any single-vertex graph $T$ is a planar graph. However, $T$ surely cannot be colored using all six ...
3
votes
1answer
68 views

Cube color matching Graph Theory problem

I'm trying to solve a problem: Suppose you are given four cubes with each of the six faces painted with one of the colors red, white, green, or yellow. Use graph theory to place the cubes in a ...
1
vote
1answer
35 views

show that χ(G)≤√(2|E|)

I was given an Homework exercise where I need to show that χ(G)≤√(2|E|) So far I've manged to prove that: 1. χ(G)+χ(G′)≤n+1 2. χ(G)≤maximin{di,i} Now I tried using (1) because I know that there's ...
3
votes
2answers
115 views

Upper Bound on the Chromatic Number of a Graph with No Two Disjoint Odd Cycles

Prove that if a graph does not have two disjoint odd cycles then χ(G) ≤ 5, where χ(G) denotes the minimum number of colors needed to color the vertices of G. χ(G) is the chromatic number of G. ...
3
votes
1answer
25 views

Prove chromatic polynomial of n-cycle

Let graph $C_n$ denote a cycle with $n$ edges and $n$ vertices where $n$ is a nonnegative integer. Let $P(G, x)$ denote the number of proper colorings of some graph $G$ using $x$ colors. Theorem: ...
1
vote
0answers
39 views

sum of chromatic numbers

How I can prove that in given simple graph G in n vertices: $$\chi(G) + \chi(\overline{G}) \leq n + 1.$$ Where $\chi$ is chromatic number. I tried to do like that: $$\chi(G) \leq \Delta(G) + 1 \;; ...
3
votes
0answers
30 views

Upper bound for the sum of chromatic number of a graph and chromatic number of its complement

I need to prove that for any simple graph $G$ on $n$ vertices the following inequality is true: $\chi(G)+\chi(\overline {G}))\le n+1$; where $G$ is a simple graph, $\overline{G}$ its complement, ...
1
vote
1answer
52 views

on the color classes of a $k$ chromatic graph

Let $G$ be a graph wich is $k$-chromatic. Suppose we have a coloring $(V_1, \ldots, V_l)$ such that each $V_i$ contains at least $2$ elements. I want to prove that $G$ has a $k$-coloring with this ...
1
vote
1answer
55 views

Number of $q$-colorings of an $n\times n$ grid graph without adjacencies

Suppose a square grid graph $g$ of side length $n$ can be colored with $q$ colors. In how many unique colorizations are no adjacent vertices the same color? A friend and I have been trying to find a ...
6
votes
0answers
79 views

Number of sets of vertices whose union of neighbours contains exactly $k$ vertices

Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows: For example, $g$ for $n=3$: If ...
3
votes
1answer
72 views

Does a colouring of a graph on two colours always have certain kinda of circle

Is there a planar set of points $P$ $(|P|\geq 4)$ such that no matter how you colour the points with two colours you can always find four points on a circle so that all four of the point have the ...
2
votes
2answers
109 views

Can the complete graph $K_9$, be 2-coloured with no blue $K_4$ or red triangles?

I am working on the following problem on 2-coloured complete graphs: $K_9$ is coloured red and blue and contains no red triangle and no blue $K_4$ then every vertex must have red degree 3 and ...
0
votes
1answer
39 views

How come that HSL can contain more information than RGB?

I have noticed weird thing when working with HSL - unlike RGB, it has some blind spots where certain value just does not matter. I'm sure we were taught about this when I had Linear algebra lectures ...
0
votes
0answers
16 views

Special partitions for cubic 3-edge connected graphs

I'm trying to prove the following A cubic 3-edge connected graph $G = (V, E)$ allows partitions $T_{i}\subset E$ such that $G\setminus T_{i}$ is 2-edge connected, for $i = 1,\ldots, 5$. In ...
1
vote
1answer
48 views

Coloring of regular graph's edges

There is a regular graph. Degree of each vertex is four. It needs to prove that edges of the graph can be colored in two colors so that each vertex is incident to two edges of the same color and the ...
2
votes
1answer
79 views

Does a colouring of a graph on two colours always have certain kinda of triangles

Is there a planar point set such that no matter how you colour the points with two colours can you can always find a triangle with exactly one point inside so that all four points have the same ...
0
votes
1answer
25 views

Colouring maximizing the weight of coloured edges

I would like to know if the following problem has been studied in the literature: We are given a edge-weighted undirected graph $G = (V,E)$ together with a set of available colours $C_v$ for each ...
2
votes
3answers
65 views

How many possible color combinations?

I have a unusual shape like this. I want to color its squares with 3 color which no two adjacent(in vertical or horizontal) squares take same color. How should I solve such problems? Please give ...
0
votes
3answers
40 views

Chess Board Coloring of a Paper using an Arbitrary Curve

Pick a piece of paper and a pen. Put the pen on a starting point and begin to draw an arbitrary curve and don't withdraw your hand until you reached the starting point. You can meet your curve during ...
3
votes
4answers
82 views

Prove $\chi(G)\chi(\bar{G}) \geq n$ for chromatic number of graph and its complement

Let us denote by $\chi(G)$ the chromatic number, which is the smallest number of colours needed to colour the graph $G$ with $n$ vertices. Let $\bar{G}$ be the complement of $G$. Show that (a) ...
1
vote
0answers
34 views

Conceptual proofs to seven color theorem of torus for 17-19 year olds

what is the best way to explain the seven color theorem of torus to some high school kids and freshman college people?
1
vote
1answer
39 views

Tiling a Square by Rectangles

I have to prove that you can't create a square with side length 10 by arranging 25 rectangles with side lengths 4 and 1, where no pair of rectangles may overlap and the whole square must be filled. ...
0
votes
0answers
18 views

Grid Points and Primes

my question is about grip points and primes. Look at the triangle $OAB$ with $O (0,0), A (p,0)$ and $B (0, p)$ and $p\in\mathbb{N}$. The points $P_i (i, p-i)$ with $i=1,\cdots, p-1$ are on $AB$. Prove ...
3
votes
1answer
36 views

Question about the proof that 'A graph with maximum degree at most k is (k + 1) colorable

I'm trying to follow the MIT introductory mathematics for cs course. In the reading on graph theory, the proof that a graph with maximum degree at most k is (k + 1) colorable is given as follows: ...
-1
votes
2answers
59 views

Coloring Graph with some constarints

if Graph G be a Cycle with Length=4. how many ways we can color this graph with at most $\lambda$ different color, in such a way that non of two adjacent vertex has a same color?
0
votes
0answers
18 views

Do these algorithms to construct the graphs with a particular property have any importance?

I found a semi-general solution to the following open-ended question and obtained the explicit algorithms to construct the graphs with the following special property. But does my solution have any ...
0
votes
0answers
9 views

Notation for the graph with edge coloring

I'm thinking of how to represent a graph with a specific edge coloring. I tried to use the following notation, but is there any other way to represent it? Let $G=(V,E)$ be a graph, and for an ...
1
vote
2answers
33 views

Graph Theory Coloring

There are some earthlings and 15 martians in a space shuttle. Each earth- ling shook hands with exactly 6 martians, and each martian shook hands with exactly 8 earthlings. How many earthlings are ...
0
votes
1answer
60 views

Edge choosability(edge list coloring) of bipartite graphs

It was proved by Galvin that the list chromatic index of bipartite multigraph $G$ equals to it's (ordinary) chromatic index: $$\chi_l'(G) = \chi'(G)$$ Let's use definition of choosability below: ...
2
votes
2answers
91 views

Prevent similar consecutive colours for a pie chart

Background Calculating colours for pie chart wedges. Consider: $$ \begin{align} d(n)&=\frac{\theta}{t}\times n\\ \end{align} $$ Where: $\theta$ is the degrees in a circle (360) $t$ is the ...
1
vote
0answers
30 views

Find the reflection point $P$

On the real number line, paint red all points that correspond to points of the form $81x+100y$, where $x$ and $y$ are positive integers. Paint the remaining integer points blue. Find a point $P$ on ...
1
vote
1answer
43 views

How many ways can we color a $7$-cycle with $3$ colors so that no three consecutive nodes are of the same color

I have to paint graph We have three colors. The constraint is that there are no three consecutive nodes of the same color. And my idea is: All ways to paint is $3^7$ I'm going to count ...
1
vote
2answers
49 views

coloring cube, additional constraint, three colors

I have to paint nodes of cube such that opposing nodes has the same color. We consider identical cubes such that rotatating. My result is $15$ Is it correct ? Ok, I 'll add my way to get a result. ...
2
votes
1answer
55 views

How many ways are there to color the $H$-shaped tree with $3$ colors such that each color is used exactly twice?

How many ways are there to color this graph with the following constraints? We have three colors: blue, red, green, and we require that the number of nodes of color green is 2, and blue 2, and red ...
0
votes
0answers
56 views

Kempe chain color swaps in a partially colored map

Crossposted to: http://mathoverflow.net/questions/179340/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using only Kempe chain color swaps (as ...
1
vote
1answer
28 views

Chromatic polynomial of a graph $G$

Let $G$ be the graph in picture: calculate the chromatic polynomial of it. My attempt: I assume that $G(K_n,x)$ is the number of distinct colors of the complete graph with $n\geq1$ vertices with ...
0
votes
0answers
34 views

Counting of edges coloring in a graph

The problem is to count of coloring graphs. We have three colors. And I found all automorphisms. It is: $$\alpha_1: (1)(2)(3)(4)(5)(6)$$ $$\alpha_2: (123456) $$ $$\alpha_3: (135)(246) $$ ...
4
votes
0answers
50 views

How many distinct chromatic polynomials are there for simple connected graphs?

For a given order $n$, the number of graphs that are determined uniquely by their chromatic polynomial is A137568. This sequence starting with n=1 is: ...
2
votes
0answers
54 views

Efficient way to count number of arithmetic progression on coloring of $\mathbb{N}$.

Consider a coloring of $\mathbb{N}$ with two colors. How many monochromatic arithmetic progressions of a fixed length $m$ (i.e. numbers of the form $a+nd$ are colored the same) are there in the subset ...
0
votes
2answers
44 views

Getting a diverse set of three numbers from two numbers

I'm using this information to build an interface to pick a color, but I feel that this question is purely math-related. Please correct me if this is the wrong StackExchange site for this. I am making ...
4
votes
1answer
44 views

Chromatic number of generalized hypercube

It's clear that the chromatic number of $Q_n$ is $2$. But what about the graph $G$ with vertex set ${n}^{(r)}$ where two vertices are adjacent if and only if their coordiantes differ by one? Can't ...
2
votes
0answers
42 views

Proof of chromatic number of a graph

Let $G$ be graph, let $x\in V(G)$ with $|\delta_G(x)|=\Delta(G)$. For all other nodes $v\in V(G)\setminus\{x\}$ let $|\delta_G(x)|\lt\Delta(G)$. Furthermore assume we have $v_1,v_2,v_3\in V(G)$ ...
0
votes
1answer
42 views

graph vertex chromatic number in a union of 2 sub-graphs

$G_1$ is graph on the set of vertices $\{1,2,3,4,5,6,7,8\}$, $G_1$ vertice chromatic number is 5. $G_2$ is graph on the set of vertices $\{7,8,9,10,11,12,13,14,15,17,18,19,20\}$, $G_2$ vertice ...
0
votes
2answers
49 views

Graph theory: graph coloring quesiton [duplicate]

$G_1$ is graph on the set of vertices $\{1,2,3,4,5,6,7,8\}$, $G_1$ vertice chromatic number is 5. $G_2$ is graph on the set of vertices $\{7,8,9,10,11,12,13,14,15,17,18,19,20\}$, $G_2$ vertice ...
2
votes
0answers
65 views

Edge choosability(edge list coloring) of cycles

I have 2 cycles with 6 length as shown below. I want to show that the above graph is 4-edge-choosable. I don't know where to start. It's known that every cycle of even length is 2-edge-choosable, ...