For questions concerned with graph colorings.

learn more… | top users | synonyms

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
35 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
34 views

circles and grid points

I have to prove that for each $n$ in $N$ is a circle that has got $n$ grip points on the periphery. I only know that I have to colour this coordinate system, haven't I? Any hint or suggestion is ...
0
votes
0answers
17 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
20 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: ...
3
votes
2answers
57 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
16 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
31 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
50 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
76 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
23 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
34 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
48 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
53 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
53 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 ...
0
votes
0answers
29 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) $$ ...
2
votes
0answers
46 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
43 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
42 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
38 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
29 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
46 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
59 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, ...
7
votes
1answer
59 views

Is it possible to partition $\mathbb{N}_+$ into a *finite* family of sets completely not closed under $+$?

Let's say that $A \subseteq \mathbb{N}_+$ is completely not closed under $+$ if $$ \forall_{a,b \in A}[{a+b \notin A}] $$ Is it possible to partition $\mathbb{N}_+$ into a finite family of sets ...
2
votes
1answer
20 views

Create a configuration - graph theory

I've encountered this (startling) difficult, to me, question: Create a configuration in the plane with a ring size 4, so that every internal vertex is of degree 5. Now, I assume I may not use ...
0
votes
1answer
34 views

3-color Graph colouring

Given a directed graph such that each node has indegree=outdegree=1 devise a algo that colour the graph such that no adjacent nodes has same color. **Note:**there is no self loop and graph has to be ...
0
votes
0answers
14 views

Chromatic polynomial for defective coloring

Is there a function for defective graph coloring (where a vertex is allowed to be adjacent to at most $d$ other vertices with the same color) that is equivalent to the chromatic polynomial for proper ...
1
vote
1answer
31 views

Number of k-colorings as a fraction of all possible ways to color a graph

I have a graph with $n$ verices, and I want to compute the number of ways to color the graph (with no adjacent vertices having the same color) using anywhere between $1$ and $n$ colors. This number ...
0
votes
0answers
46 views

$k$-coloring problem which minimizes the number of conflicting vertices

Classical $k$-coloring problem (k-GCP) is to assign a color selected from $k$ colors to each vertex of graph $G$ so that the number of conflicting edges (the edges with same color endpoints) is ...
6
votes
6answers
708 views

Why doesn't $255 \times 255 \times 255 = 16777215$

Ok, I obviously understand basic multiplication and understand why those don't equal. But in web colors, therr is FFFFFF hexadecimal different colors (or rather $16,777,215$ in base $10$). This amount ...
0
votes
1answer
38 views

Complex Combinatorics Hexagon/Triangle Contest Problem

The problem is as follows: The six sides of convex hexagon $A_1A_2A_3A_4 A_5A_6 $ are colored red. Each of the diagonals of the hexagon is colored either red or blue. Compute the number of colorings ...
0
votes
0answers
62 views

Kempes' Flaw on 4 Color Theorem.

In The Beginner's Guide to Graph Theory by Wallis, the author introduced the flaw of Kempes' attempt to proof the four-color theorem: Kempe assumed that $G$ is a minimal planar graph requiring five ...
1
vote
0answers
29 views

If G compliment is disconnected, then chromatic number = circular chromatic number

I've been reading through a book called graph homomorphism and this is an exercise I've been trying to prove. Here's my work so far Induction on number of vertices Basis : this clearly holds ...
1
vote
0answers
45 views

Flows in signed graphs and coloring

Nowhere-zero flows and coloring of planar graphs are related by duality. (wiki) I heard that there was a similar relation for nowhere-zero flows in signed graphs and colorings of some other graphs. I ...
3
votes
1answer
40 views

Finding the number of possible ways to 'paint' a geometry

Problem: Find the number of possible ways to paint $n$ sectors of a disk with $n$ color brushes to differentiate all $n$ sectors. (i.e., you cannot paint an adjoining sector with the same color) ...
1
vote
1answer
43 views

coloring of a graph after removing a vertex

Let $G$ be any simple graph (i.e has no loops nor multiple edges) and let $1,2,...,\chi(G)$ be any good coloring to the vertices of $G$(i.e a minimal coloring for its vertices in which each 2 adjacent ...
0
votes
1answer
29 views

Elementary graph coloring

I have recently been introduced to graph theory, and there is that one idea I have which I am struggling with. I would like to know if this is true, and whether or not there is a somewhat simple proof ...
1
vote
1answer
32 views

Coloring a binary tree

Working through a problems practice coloring, I have found a problem that has me stumped. The problem states: For $n \in \mathbb{R}_{>o}$ the binary tree is defined recursively as follows. The ...
1
vote
1answer
44 views

Calculating Total Number of Possible 4-Colorings of a Graph

I recently met with a professor to discuss this problem and she didn't have an answer for how to do the calculation. What I did learn is that the counting itself is considered NP-Hard and is in a ...
1
vote
0answers
37 views

Which in graph theory book do you recommend for a Biologist?

I need a book in Graph Theory for my Thesis project in Biology (6 months from now). I have reasonable mathematical knowledge. The book must be strict but not as complicated as an advanced book. The ...
3
votes
1answer
46 views

Colouring bipartite graph with sets of possible colors to each vertex

I'm having some trouble with proving the following: Let $|S(v)|$ be the set of colours available to colour vertex v. The claim is that for every bipartite graph $G=(V,E)$, if $|S(v)| > log_2n$ for ...
0
votes
1answer
88 views

Five-coloring plane graphs

These days I've been reading about graph coloring. Right now I'm dealing with the five color theorem. I know how to prove that every planar graph is 6 and 5 colorable. I'm looking on the proof of the ...
0
votes
1answer
14 views

Removing a vertex from a non k-colorable graph cannot make it (k−2)-colorable

This is supposidly True in the key but a pentagon is non-4-colorable and removing a vertex (either deletion or contraction) leaves a 2 colorable graph. anyone know anything about this or is it just ...
0
votes
1answer
48 views

Number of ways to colour a square with n colours

A smaller square is centered inside of a larger one. If we paint the edges of the outer square and the corners of the inner square, then how many distinct ways are there to colour the squares, ...
0
votes
1answer
31 views

Show that cubic hamiltonian graph is edge-3-colourable.

How can I show that cubic hamiltonian graph is edge-3-colourable?
0
votes
0answers
32 views

Cube formation and face-color identification

Six squares are colored, front and back, Red (R), Blue (B), Yellow (Y), Green (G), White (W) and Orange (O) and are hinged together as shown in figure. If they are folded to form a cube, what would be ...
2
votes
1answer
358 views

Best way to plot a 4 dimensional meshgrid

I have $4$ variables $X$, $Y$, $Z$ and $C$, and I want to plot these on a graph. Usually I would just plot the surface $X$, $Y$, $Z$ and then use color to represent the $4$th dimension, as shown ...
1
vote
0answers
68 views

Proof of Gallai's Theorem for Critical Graphs

A fundamental theorem in Graph theory is the following: Let $G$ be a $k$-critical graph with $k\geq 4$ and $G\neq K_k$. Then every block in the subgraph of $G$ induced by the vertices of degree $k-1$ ...
2
votes
0answers
51 views

References for chromatic symmetric functions of hypergraphs

Define a hypergraph to be a pair $H = (V,E)$ where $V$ is a set of vertices and $E$ is any set of subsets of $V$ called edges. Thus if every edge $U \in E$ has only two elements, then the hypergraph ...