# Questions tagged [coloring]

For questions concerned with graph colorings.

1,079 questions
Filter by
Sorted by
Tagged with
19 views

### Chromatic Polynomial and Chromatic Number of this graph [closed]

Determine the chromatic polynomial for the following graph and deduce the chromatic number:
27 views

### Prove that every hamiltonian planar graph is 4 face coloreable. [closed]

I was thinking about using the 4 color theorem but I don't know how it would work, also I know that a graph is hamiltonian if it has a hamiltonian cycle (a cycle that visits every vertex once), but it ...
21 views

### rectangular cube with the same color vertices [closed]

we colored the space points with n color. prove that a rectangular cube with the same color vertices is found. it means we can find 8 points in the space colored with n color which form a rectangular ...
15 views

### Using chromatic polynomial find the chromatic number of any connected graph with at least 5 vertices (any graph you can think of).

I know what chromatic number is, but am unfamiliar with chromatic polynomial and don't know how to use it to get the chromatic number. Any help? Thanks!
54 views

### Number of ways of arranging 10 tiles in four colors such that any consecutive block of 5 tiles contain all four colors

This problem is from Purple Comet High school contest, 2016. Ten square tiles are placed in a row, and each can be painted with one of the four colors red (R), yellow (Y), blue (B), and white (W). ...
30 views

### Construct the proof five color theorem using graphical illustration [closed]

I have been studying graph coloring but i have no idea to prove this. graph
15 views

### Question about coloring a Cube [closed]

The vertices of a cube are numbered from $1$ to $8$. (a) What are all the elements of $S_8$ which correspond to symmetries of the cube? (b) How many ways the vertices of the cube can be coloured ...
26 views

### Intersection of lines in the plane

Consider the set of lines in the plane such that no three pass through the same point and let $G$ be the graph how many vertices are the intersections of the lines, and where two vertices are adjacent ...
31 views

### Doubt about chromatic number proof

I'm in a discrete math course and was trying to prove the following theorem: A graph G with $\Delta(G) = k$ ($\Delta(G)$ is the max vertex degree) is $(k+1)-$coloreable. I've tried my own, and I'...
42 views

### Graph coloring problem. Let $G$ be $|V(G)| = n$ and $k$-colorable.

Let $G$ be $|V(G)| = n$ and $k$-colorable. Show that G has a independent set with at least $\frac{n}{k}$ vertices. An Independt set is a set of vettex that have the same color such that for every 2 ...
28 views

### Show that $G_1 + G_2$ is critical if and only if $G1$ and $G_2$ are critical.

Let $G_1$, $G_2$ be two graphs, show that: $G_1 + G_2$ is critical if and only if $G1$ and $G_2$ are critical. Remember that:we say that a graph $G$ is critical si $χ(H) < χ(G)$ for every ...
66 views

43 views

### Chromatic number of a graph on a chess board

For a chess piece Q, the Q-graph is the graph whose vertices are the squares of the chess board and the two squares are adjacent if Q can move from one of them to the other in one move. Find the ...
30 views

### Is every perfect graph $G$ a union of $\omega(G)-1$ bipartite graphs?

If any perfect graph $G$ has no $n+1$ clique then can one always find $n$ bipartite graphs $B_1,\ldots B_n$ such that $G=\cup_{k=1}^nB_k$?
48 views

### Reduction from a m-coloring to a m-partition

define a m-partition as: Given an undirected graph G = (V, E) and an integer j. Does there exist a partition of the vertices into m parts {V1, V2, ... , Vm} such that at least j of the edges have ...
38 views

### Lower bound for The chromatic index of the complete graph of order n, where n is odd.

How can I prove that the chromatic index i of the complete graph of order n, where n is odd, is i > n-1. I found here a construction with n colors, but am having a hard time to prove lower bound.
30 views

### Vertex List Coloring Algorithm

Is there any (preferably simple) algorithm to check list-coloring for small planar graphs? I searched and found many bounds-on-list-chromatic numbers and some results on edge list coloring. I could ...
23 views

### Chromatic Number of Graph after Removing Vertex Proof

Show that χ(G − v) is either χ(G) or χ(G) − 1. χ is the chromatic number of a graph, G is the graph, v is a vertex. I am trying to prove this, using a 2 case method for the two options, but I cannot ...
12 views

### Vertex coloring of non simple line arrangement

Given a plane with lines intersecting each other, and there is no limit on how many lines can intersect at one point. We make graph $G$ from such line arrangement. Prove that $\chi(G)\leq4$ without ...
55 views

### Proving Chromatic number is either X(G) or X(G)-1

Alright it is exam season and I need some help studying. I can't get this problem Let G be a graph and v be a vertex in G. Show that the chromatic number X(G-v) is either X(G) or X(G)-1. Thank you.
23 views

### Chromatic polynomial of the $1$-skeleton of the $24$-cell

I'm interested in computing the chromatic polynomial of the $24$-cell. Trying to compute this in Mathematica in a naïve way (...
11 views

### Counterexample to sequential edge-coloring algorithm?

There is an algorithm to find the edge-coloring of a graph: This is supposedly a greedy algorithm, but is there a counter-example when this algorithm doesn't produce a minimum edge-coloring?
Let $S$ be a set with $2020$ elements, and let $N$ be an integer with $0 \le N \le 2020$ . Prove that it is possible to color every subset of $S$ either black or white so that the following ...
Given a graph $G$, i have to talk about the number of ways to color this graph properly (so that no adjacent vertices have the same color). As an algorithm, i used the "Welsh-Powell" Algorithm. I have ...