# Tagged Questions

For questions concerned with graph colorings.

25 views

### Proving that $\chi(G) = \omega(G)$ if $\bar{G}$ is bipartite.

I know that $\chi \! \left( \bar{G} \right) = 2$ and that $\chi(G) \geq \alpha \! \left( \bar{G} \right)$, but how can I conclude that $\chi(G) = \omega(G)$?
24 views

### How to prove k-colorablity of G by considering $G$ x $K_k$? [on hold]

How can I prove that a graph G with n vertices is $k$-colorable iff $\alpha$(G x K$_k$) $\geq$ n? The necessity seems clear since the set of vertices which have the same color in G x K$_k$ is ...
10 views

### Prove Graph G is in Vizing Class 2 if $\alpha$'(G) < |e(G)|/$\Delta$(G)

G is a simple graph with e edges, maximum vertex degree $\Delta$ and edge independence number $\alpha$' which satisfies $\alpha$' < e/$\Delta$. What does this inequality mean? How is it helpful in ...
135 views

### Upper bound for chromatic number related to number of edges [closed]

Prove that in any simple, undirected graph $G=(V,E)$, the chromatic number $χ(G)≤ \sqrt{2m} +1$, where $m=|E|$
21 views

### Prove that there is a red triangle or a blue triangle that is is a sub-graph

If the edges of $K_6$ are coloured blue or red, prove that there is a red triangle or a blue triangle that is a sub-graph. Well I am having a hard time proving this, I try to prove it by ...
31 views

### How can I prove that if $S$ any independent set of $G$ and $G$ is color critical then $\chi(G−S)=\chi(G)−1$

Let $G$ be a color critical graph and $S$ any independent set of $G$ then $\chi(G−S)=\chi(G)−1.$ I tried to show that any independent set induce one color, but I cannot match it with the color ...
18 views

### Can a certain board be covered in Tetrominoes

Prove that a $15x8$ board cannot be covered by $2$ L-tetrominoes and $28$ skew tetrominoes. This is a coloring proof and I have tried a variety of colorings, from stripe colorings to other unique ...
25 views

### Non-adjacent vertices have different colour? [closed]

In a proper vertex coloured graph, can two non-adjacent vertices have different colours?
44 views

### Colorability of planar graphs.

I'm trying to show that every planar simple graph with no cycles of length {4,5,6,7,8,9,10,11} is 3-colourable. Here is what I've done so far. Let S be the set of all graphs for which the statement ...
47 views

### Color the set of integers with four colors

Show that one can color the set of integers with four colors: blue, red, yellow and purple, such that for any four numbers with the same colors $a, b, c, d$ (not necessarily distinct, not all four of ...
47 views

### Ball Colouring problem clarification

Before you downvote this for being a duplicate, kindly take cognisance of the face that I don't have enough reputation to comment on the germane answer.I'll attempt to pose my enquiry as a question In ...
39 views

### Why is the constant term in any chromatic polynomial is always zero?

The chromatic polynomial $P(G,\lambda)$ is simply the number of different way in which we can colour a graph $G$ with at-most $\lambda$ different colours. Such that every pair of adjacent vertices ...
38 views

### Are these graph coloring algorithms equivalent?

Suppose you want to color the vertices of a graph in a greedy fashion, given a predetermined order of these vertices. I am wondering if these two algorithms are equivalent: Algorithm 1: Consider ...
21 views

### Is it possible for 8 different numbers to exist that when combined form unique results?

I am wrestling with a question relating to colors, specifically hexadecimal color codes. A hexadecimal color code is represented in three parts, Red, Green, and Blue, all ranging from 0-255. These ...
23 views

### Is it necessary that the chromatic polynomial must be a function of K and N?

Is it a necessary condition that we must use the K (number of colors) and N (number of vertices) to make the chromatic ...
40 views

### A plane is colored with three colors. Prove that there exists a right triangle on this plane, having vertices of the same color.

I got stuck with this idea in mind that I could find a shape with all of the vertices connected to each other and all of its angles being 90 degrees. One of such shapes which is not correct is as ...
68 views

### Chromatic number of complement of Petersen graph

Hello ladies and gentlemen. This is Petersen Graph - It is an undirected graph, it is $3$-regular and it's chromatic number is $3$. Proof: There is a circle with $5$ nodes (the outside pentagon), a ...
21 views

### Interesting planar graph coloring task - estimate colours for double planar graph

I got an interesting exercise on my course at University. I am wondering about an answer and I would like that some people would wonder with me. Because there may be not clear answer even. So.. as ...
18 views

### 3 face colorability of a trivalent bipartite graph embedded on a torus

Is a cubic bipartite graph embedded on a torus always 3 face colorable? This is true for a planar graph. We can prove it on the dual graph by considering triangulation of an Eulerian graph and then ...
30 views

### Chromatic Number Of A Random Graph

Does anyone know what the chromatic number of a graph chosen randomly on n vertices is, as n tends to infinity? I mean, almost all graphs have chromatic number greater than any fixed k. But in terms ...
27 views

### A Question about Chromatic numbers and the size of the largest Independent set in a graph.

From my textbook for Graph Theory: a) If $q$ is the size of the largest independent set in a graph $G$, show that $\chi(G) \cdot q \geq n$, where $n$ is the number of vertices in $G$. b) If the ...
16 views

### Explicit graphs with large chromatic number and girth

It is well known that there exist graphs with large chromatic number and girth. More precisely, for any $k$ and $l$, there exists a graph $G$ such that $\chi(G) > k$ (where $\chi$ denotes the ...
40 views

### Why is Welsh-Powell algorithm better than the basic greedy algorithm for graph coloring?

I am not able to find any reason that why Welsh-Powell algorithm works better than the basic greedy algorithm for graph coloring. In Welsh-Powell algorithm, the only thing that differs from the basic ...
37 views

A $23\times23$ square is completely tiled by $1\times1, 2\times2$ and $3\times3$ tiles. What is the smallest number of $1\times1$ tiles needed? This is the solution If we color the rows of the ...
146 views

### Is Unit McGee rigid?

I figured out a unit distance embedding for the McGee graph. Bram Cohen asked me if it's rigid. I had a hard enough time figuring out this one embedding. If some points can move around, I might ...
77 views

### Lower bound for $R(3, 3,\ldots, 3)$

As part of learning Ramsey numbers I am trying to prove that $R(\underbrace{3, 3,\ldots, 3}_{k\text{ times}}) > 2^k$ using the constructive method. In order to do that one needs to colour the edges ...
46 views

### Prove that a simple, connected graph with odd vertices has edge chromatic number $\Delta + 1$

I'm struggling to see how this can be right when I consider the simple example of a three vertex graph such that one vertex has one edge each with the other two vertices. Such a graph is connected and ...