# Questions tagged [coloring]

For questions concerned with graph colorings. (This is not for mathematical art.)

1,557 questions
Filter by
Sorted by
Tagged with
56 views

### Sum of squares of chromatic roots of a bipartite graph

Given a graph $G = (V, E)$, we can calculate its chromatic polynomial $P(G, k)$, and it has $n$ (complex) roots, also known as chromatic roots. It is a well-known fact that the sum of chromatic roots ...
105 views

### Icosahedron with asymmetric coloring

I am trying to determine the number of unique solutions when placing "dots" on the sides of an icosahedron. There can be up to three dots placed symmetrically on each side. The dots are ...
82 views

### Combinatorics board olympiad problem Rioplatenes P3

Each square of a 100 x 100 square board was painted some color, so that no line (row or column) has more than 4 different colors. What is the maximum number of colors that could have been used? ...
19 views

### If G is a bipartite graph with 6 vertices and 9 edges then the chromatic number of G bar? [closed]

Here for bipartite graph chromatic number will be the 2 but if we have 6 vertices and 9 edges then it will become complete bipartite graph so its complement graph will be the null graph. So, its ...
65 views

### Proof or Counterexample: A ($K_3$,$C_5$)-free graph has fractional chromatic number at most 7/3.

Claim. A triangle-free simple undirected graph $G$ without an induced 5-cycle $C_5$ satisfies $\chi_f(G)\leq 7/3$, where $\chi_f(G)$ denotes the fractional chromatic number. The question is ...
1 vote
34 views

1 vote
20 views

### Welsh-Powell coloring algorithm is better in most cases, or all cases?

I have checked past results (including the original paper from Welsh-Powell), and other sources by googling, and saw that the ordering of the vertices based on descending degrees is not needed for the ...
16 views

### Neighborhood of a complete graph and k-critical Colouring

Found this question "Suppose $u, v ∈ V$ are such that $N (u) ⊆ N (v)$, prove that $G$ is not $k$-critical for any $k$" Now if $G$ was a complete graph $K_n$ such as $K_5$ where there are 5 ...
67 views

### Graph Drawings (The graph not being regular is throwing me off) [closed]

A graph $G$ with $\chi(G) = 3$ and $G$ is not regular. I am attempting to draw a graph with chromatic number $3$, that is irregular, would a Peterson graph apply to this situation
81 views

### 3 points blue, red, green form a triangle $T$ in $\mathbb R^2$. 3 points B, R, G inside that triangle. Do all proper rainbow triangles cover $T$?

Suppose I have 3 points colored blue, red, and green resp. forming a triangle $T$ in $\mathbb R^2$. Suppose I have 3 more points colored blue, red, green resp. (possibly overlapping) in the interior ...
113 views

### Monochromatic equilateral triangles in a 2-colored circle

Problem. Suppose every point of a circle (with a fixed radius) has been colored either red or blue. Does there exist an equilateral triangle whose 3 vertices are on the circle and share the same color?...
1 vote
29 views

### Using independence number of a graph to prove inequality statement [duplicate]

The independence number of a graph $G$, denoted $α(G)$, is the maximum number $k$ such that $G$ contains a set of $k$ nonadjacent vertices. Noting that “color classes” are sets of nonadjacent vertices,...
34 views

### Proving the possibility of building a three-colorable graph with n vertices

I want to show that, for every number n, it is possible to build a three-colorable graph with n vertices and $\left\lfloor \frac{n^2}{3} \right\rfloor$ edges. I also want to show that if you have any ...
61 views

### Calculating chromatic polynomial of a general graph $G$

Proposition 5.3.4 from Introduction to Graph Theory, Second Edition, Douglas B. West. Let $x_{(r)} = x(x-1)...(x-r+1)$. If $p_{r}(G)$ denotes the number of partitions of $V(G)$ into $r$ non empty ...
69 views

### Every k-chromatic graph has a k-critical subgraph

I came across this result stated as a fact in Introduction to Graph Theory by Douglas B. West. Intuitively this looks obvious but I am struggling to find an algorithm to find this. If G itself is k-...
I want to show that I can you can build a two-colorable graph for all n that have n vertices and $\left\lfloor \frac{n^2}{4} \right\rfloor$ edges. After this, I want to show that it is impossible to ...
### Suppose $G$ is a graph with $n$ vertices and $G$ has no 5-cycle, show that the chromatic number of $G$ is $O(\sqrt{n})$
Suppose $G$ is a graph with $n$ vertices and $G$ has no 5-cycle, show that the chromatic number of $G$ is $O(\sqrt{n})$. That is, if $G$ has $n$ vertices and has no 5-cycle, there is some constant $c$ ...