For questions concerned with graph colorings.

learn more… | top users | synonyms (1)

2
votes
1answer
28 views

Chromatic number and vertex covering number

For any graph $G=(V,E)$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$. Let $\chi(G)$ denote the chromatic number of $G$. Is there a graph $G$ with $\tau(G) < \chi(G) - 1$?
0
votes
1answer
24 views

Confusion about Hajós construction?

I've read this article on the Hajós construction. I've tried to execute it in a small graph to see it's results, I guess it would be something like this: These are the incidency matrices of $G,H$ and ...
1
vote
1answer
19 views

If edges of $G$ are two colored, then there is a vertex of $G$ with at most two col0or changes in the cyclic order of the edges around the vertex.

Hello there i am reading proofs from the book of Gunter M ziegler. The chapter is called Three applications of eulers formula. Know there is a proposition which i don't fully understand and help would ...
3
votes
1answer
32 views

Every graph can be optimally colored greedily.

I was at a conference today and someone said that if the graph $G$ has chromatic number $n$ then there is a way to order the vertices so that coloring greedily gives us a coloring with $n$ colors. By ...
1
vote
1answer
31 views

Calculating chromatic polynomial for a graph

This is the graph I'm trying to find its chromatic polynomial when $\lambda = 3$ This is my solution, first take look at this theorem: Theorem : If $G = (V,E)$ is a graph and $G_1 , G_2$ are ...
0
votes
0answers
30 views

Polynomial time algorithm for finding the chromatic sum of a tree.

As the title goes, a polynomial time algorithm for finding the chromatic sum of a tree is required. NOTE: Finding the chromatic sum of a graph is also called the sum coloring problem - The sum ...
1
vote
0answers
20 views

Twisted colouring problem

I had doubts in the following similar looking questions I came across:- $Q1.$ The Cartesian plane is coloured with 2 colours. Prove that there exists 3 points of the same colour, which are the ...
0
votes
1answer
20 views

Chromatic number of a map

Since in the map each state is connect to another state we are dealing with a complete graph ($K_{12}$). Since, it is a complete graph (every state is connected to every other state), every vertex ...
0
votes
0answers
19 views

If I colour n vertices independently, randomly with n^(1-x) colours, why is the size of the colour classes (1+o(1))n^x?

By o(1), I mean 'little-o' of 1. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.
15
votes
3answers
326 views

Is it possible to uniquely number faces of a hexagonal grid with consecutive numbers?

You have a grid of regular hexagons. The aim of the game is to have each hex contain the numbers 1-6 on its edges. Each edge must also be connected to another edge that has a value one higher and ...
1
vote
0answers
28 views

Comparison with the greedy algorithm

Consider the following algorithm to vertex coloring: First find a maximal independent set of vertices and color these with the color 1. Then find a maximal independent set of vertices in the remaining ...
1
vote
1answer
20 views

Is there a name for this graph density measure?

Let $G=(V,E)$ be an undirected graph. We define the following procedure (randomized greedy coloring): Fix some random ordering over the vertices (each permutation will be chosen w.p. ...
2
votes
0answers
29 views

Mixing time for metropolis chain on graph coloring

I'm reading the Markov Chains and Mixing Times by David Levin et al.. In section 5.4 page 71 a proof is given for a bound of mixing time for the Metropolis Chain on graph coloring. In the proof, such ...
3
votes
1answer
159 views

Prove or disprove this upper bound on chromatic number.

Let $G$ be a simple connected finite graph and let $v \ge 4$ be the number of vertices, $E$ the number of edges, $\chi(G)$ the chromatic number , $\omega(G)$ the clique number and $\Delta$ the ...
2
votes
1answer
44 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
34 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
30 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
45 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
58 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
16 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
104 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
38 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
135 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
29 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
44 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
41 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
58 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
58 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
85 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
73 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
113 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
41 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 ...
1
vote
0answers
19 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
50 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
82 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
28 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
74 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
44 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
109 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
42 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
19 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
56 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
20 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
12 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
34 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
66 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
107 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
32 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 ...