Skip to main content

Questions tagged [coloring]

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

Filter by
Sorted by
Tagged with
17 votes
2 answers
2k views

How many 2-edge-colourings of $K_n$ are there?

I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially ...
Clum's user avatar
  • 171
11 votes
3 answers
12k views

the Nordhaus-Gaddum problems for chromatic number of graph and its complement

Is there any relation between the chromatic number of a graph $G$ and its complement $G'$ that are always true? I saw these ones: $\chi(G)\chi(G')\geq n$ and $\chi(G)+\chi(G')\geq 2n$, but I'm not ...
Abd's user avatar
  • 111
14 votes
3 answers
6k views

Edge coloring of the cube

We have a cube and we are coloring its edges. There are three colors available. We say that the two colorings are the same if one can obtain a second by turning cube and permuting colors. Find the ...
xan's user avatar
  • 1,453
10 votes
1 answer
6k views

Inequality between chromatic number and number of edges of a graph

I have not been able to find a proof to the statement that if a graph $G$ has $\chi(G)=k$, then it must have at least $\binom{k}{2}$ edges. Would you be able to show me a simple proof?
Aria Fitzpatrick's user avatar
7 votes
2 answers
4k views

Construction of a triangle-free graph of chromatic number $1526$

I found this exercise in Bollobas: Modern Graph Theory "Construct a triangle-free graph of chromatic number 1526" It is added not to use results from the chapter about Ramsey Theory. Now my ...
Montaigne's user avatar
  • 875
4 votes
2 answers
3k views

Coloring dodecahedron

I found some months ago that there are the Polya's enumeration theorem to compute number of colorings of dodecahedron. I got interested to find how to show by using only Burnside's lemma that there ...
Jaska's user avatar
  • 127
5 votes
2 answers
7k views

How to find chromatic number of the $n$-dimensional hypercube $Q_n$?

How to find chromatic number the $n$-dimensional hypercube $Q_n$? I know $\chi(Q_2)$=2 , $\chi(Q_3)$=2 , $\chi(Q_4)$=4
World's user avatar
  • 413
25 votes
4 answers
17k views

Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle?

I have a $3$-coloring of $\mathbb{Z}\times\mathbb{Z}$, i.e. a function $f:\mathbb{Z}\times\mathbb{Z}\to\{\color{red}{\text{red}},\color{green}{\text{green}},\color{blue}{\text{blue}}\}$. I have to ...
user avatar
20 votes
2 answers
3k views

Monochromatic squares in a colored plane

Color every point in the real plane using the colors blue,yellow only. It can be shown that there exists a rectangle that has all vertices with the same color. Is it possible to show that there exists ...
Amr's user avatar
  • 20.1k
19 votes
4 answers
19k views

Edge-coloring of bipartite graphs

A theorem of König says that Any bipartite graph $G$ has an edge-coloring with $\Delta(G)$ (maximal degree) colors. This document proves it on page 4 by: Proving the theorem for regular ...
Klaus's user avatar
  • 4,115
9 votes
1 answer
19k views

Coloring a $3\times n$ board using $3$ colors

I have been reading about Combinatorial Material for a while now. I also solved a few examples. However am stuck at this one. Find the total number of ways a $3 \times n$ board can be painted ...
guthik's user avatar
  • 429
12 votes
1 answer
4k views

Upper bound on $\chi(G)$ for a triangle-free graph

I'm struggling with the following question; For every graph $G$ such that $K_3 \not\subseteq G$ (i.e. $G$ does not contain a triangle), prove that $\chi(G) \leq 2\sqrt{n} +1$ (where $\chi(G)$ ...
rm95's user avatar
  • 341
8 votes
3 answers
2k views

When chessboards meet dominoes

You probably have heard about the following brainteaser : Consider a $8\times 8$ chessboard. Remove two extreme squares (top-left and bottom-right e.g.). Can you fill the remaining chessboard with $...
vanna's user avatar
  • 1,524
5 votes
1 answer
5k 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: $P(...
Joel Christophel's user avatar
4 votes
3 answers
4k views

Chromatic polynomial of a grid graph

I have the following graph with $nm$ vertices: ...
Indradhanush Gupta's user avatar
4 votes
2 answers
612 views

Is this braced heptagon a rigid graph?

In Mathematica, GraphData[{"UnitDistance", {21, 2}}] Is this 42-edge graph rigid? It has chromatic number 4. If it was floppy, that might make it an interesting tool in high-chromatic ...
Ed Pegg's user avatar
  • 21.2k
4 votes
1 answer
774 views

Formula for coefficient of $x^{n-2}$ in the chromatic polynomial of a graph

I'm currently working on the following graph theory problem: Let $G$ be a graph of order $n \geq 3$ and let $p_G(x)=\sum_{i=0}^{n-1} (-1)^ia_ix^{n-i}$ be the chromatic polynomial of G. Show that $a_2=...
NatNat's user avatar
  • 332
0 votes
1 answer
310 views

Prove that $\chi(G) \le n$ just when there is a homomorphism from the graph $G$ to $K_n$

I would be very grateful for help with this proof: Prove that $\chi(G) \leq n$ just when there is a homomorphism from the graph $G$ to $K_n$. We know that $\chi(G)$ denotes the minimum of colors ...
Math07's user avatar
  • 51
97 votes
6 answers
4k views

Graph theoretic proof: For six irrational numbers, there are three among them such that the sum of any two of them is irrational.

Problem. Let there be six irrational numbers. Prove that there exists three irrational numbers among them such that the sum of any two of those irrational numbers is also irrational. I have tried to ...
Arpon Basu's user avatar
  • 1,171
8 votes
1 answer
5k views

Prove, that graph $G$ has at least $\chi(G)(\chi(G)-1)/2$ edges.

Can anybody give me any hints about how to prove that for any graph $G$ the number of edges in it is at least $\chi(G)(\chi(G)-1)/2$? $\chi(G)$ is the minimal number of colors we need to use to color ...
Arek Krawczyk's user avatar
8 votes
2 answers
968 views

Coloring grid points with two colors

Let $S$ be a set of finite many grid points (points in the coordinate system with integer coordinates). Is it always possible to color them with two colors, red and blue, such that in each vertical ...
user173628192's user avatar
7 votes
1 answer
12k views

Chromatic polynomial for a bipartite graph

I need to get the chromatic polynomial for the complete bipartite graph: $K_{2,3}$ Im using the Fundamental Reduction Theorem, and the picture below shows mi attempt to it. I omitted vertex names ...
Wyvern666's user avatar
  • 911
6 votes
1 answer
583 views

Number of distinct proper minimal edge colorings of a labeled complete graph

It seems like the answer to this question ought to be well-known, or at least some conjectures made if it's unsolved, but my searches so far have come up empty. In how many ways may we color the ...
Doug Torrance's user avatar
5 votes
1 answer
334 views

An $m$ coloured graph must have a path with each vertex taking up one colour each

Suppose that the chromatic number of graph $G$ is $m$ and $c\colon \operatorname{V}(G) \to \{1,2,3,\dotsc,m\}$ is a proper $m$-coloring of $G$. Then must there be a path $x_1, \dotsc, x_m$ in $G$ with ...
user381198's user avatar
5 votes
2 answers
2k views

Size of a $3$-colored square grid to produce a monochrome rectangle

Given a square grid, dimension $k\times k$, how big does $k$ have to be so that a $3$-coloring will always produce a monochrome rectangle - a set of some four same-colored points of the grid in a ...
Joffan's user avatar
  • 39.8k
4 votes
2 answers
4k views

Coloring Graph Problem

If G is a graph containing no loops or multiple edges, then the edge-chromatic number $X_e(C)$ of G is defined to be the least number of colours needed to colour the edges of G in such a way that no ...
World's user avatar
  • 413
4 votes
1 answer
6k views

Prove that the Petersen graph does not have edge chromatic number = 3.

Explain why the Petersen graph cannot have its edges coloured with exactly 3 colours so that adjacent edges receive different colours. I know that this is true by looking at the graph, but I'm having ...
pretty fly for a pi guy's user avatar
3 votes
2 answers
2k views

Tree Graphs Colorings With K Colors

For each of the trees, how many different ways are there of coloring the vertices with k colors such that adjacent vertices are colored with different colors and so that two colorings of the graph are ...
Mahlissa LECKY's user avatar
2 votes
2 answers
3k views

Chromatic Polynomial

I am asked the following: Let n be a positive integer at least 3. The wheel W_n is the graph obtained by taking the cycle C_n, placing an additional vertex at the center, and joining it to ...
Nick's user avatar
  • 489
2 votes
2 answers
1k views

Upper bound on chromatic number characterization with longest directed path

"Show that $\chi (G)\leq k$ if and only if $G$ admits an orientation such that the longest path has length at most $k-1$." The greedy algorithm may be helpful for proving one direction of the ...
james's user avatar
  • 21
1 vote
1 answer
682 views

Connected graph with colored edges

We have connected undirected graph with colored edges in two way (green or blue). And also each vertex have the same number of green and blue edges. How to prove that there are alternate colored (...
M. Red's user avatar
  • 350
1 vote
1 answer
240 views

How to count the closed left-hand turn paths of planar bicubic graphs?

When you draw a planar cubic bipartite graph $\Gamma$ and 3-color its edges you can use this as an orientation $\mathcal O$. Definition A left-hand turn path on $(\Gamma, \mathcal O)$ is a closed ...
draks ...'s user avatar
  • 18.5k
42 votes
6 answers
22k views

Four color theorem disproof?

My brother in law and I were discussing the four color theorem; neither of us are huge math geeks, but we both like a challenge, and tonight we were discussing the four color theorem and if there were ...
Doktor J's user avatar
  • 651
15 votes
2 answers
604 views

"Math Lotto" Tickets - finding the minimum winning set

"Math lotto" is played as follows: a player marks six squares on a 6x6 square. Then six "losing squares" are drawn. A player wins if none of the losing squares are marked on his ...
Asher2211's user avatar
  • 3,414
14 votes
1 answer
621 views

5-color coloring game.

Let there be two players, $A$ and $B$, and a map. They now play a game such that: Player $A$ picks a region and player $B$ colors it such that the region is a different color than all adjacent ...
blademan9999's user avatar
12 votes
1 answer
23k 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: ...
mallardz's user avatar
  • 245
11 votes
1 answer
1k views

On the four and five color theorems

The five color theorem for planar maps is considerably easier to prove than the four color theorem. The essential part of the proof is the Kempe-Heawood swap: given coloring of a map, choose two ...
DVD's user avatar
  • 1,157
11 votes
3 answers
14k views

Chromatic index of a complete graph

Looking to show that $\forall n \in \mathbb{N}$ $$\chi^{'}(K_{2n+2})=\chi^{'}(K_{2n+1})=2n+1$$ I'm trying to construct a colouring of the edges of $K_{2n+1}$ that leaves colour $i$ missing at vertex ...
John Fernley's user avatar
  • 1,228
11 votes
2 answers
6k views

Graph theory: Prove $k$-regular graph $\#V$ = odd, $\chi'(G)> k$

I'm looking to prove that any $k$-regular graph $G$ (i.e. a graph with degree $k$ for all vertices) with an odd number of points has edge-colouring number $>k$ ($\chi'(G) > k$). With Vizing, I ...
FreshmanMath's user avatar
6 votes
2 answers
361 views

How many words can be made with $7$ A's, $6$ B's, $5$ C's and $4$ D's with no consecutive equal letters.

I would like to know how many $22$ letter words can be made that have exactly $7$ A's, $6$ B's , $5$ C's and $4$ D's and have no consecutive letters the same. This problem is clearly equivalent to ...
Asinomás's user avatar
  • 106k
6 votes
1 answer
1k views

The chromatic number of a graph is at most its circumference

The chromatic number of a graph is at most its circumference: the length of the longest cycle in the graph. (Making an exception for forests, where the chromatic number is at most $2$ and the ...
Misha Lavrov's user avatar
5 votes
1 answer
451 views

Combinatorial proof that chromatic polynomial of $n$-cycle is $(x-1)^n+(-1)^n(x-1)$.

How we can proof that chromatic polynomial of cycle $C_n$ is $$ w(x) =(x-1)^n+(-1)^n(x-1) $$ I saw algebraic proof but I am really interested in combinatoric proof of this fact We choose random ...
trolley's user avatar
  • 835
5 votes
2 answers
293 views

Upper bound for chromatic number of partitioned graph.

Let $G=(V,E)$ be a graph that satisfies: $(1)$ $V= \dot\cup_{k=1}^n V_k.$ $(2)$ For all $i,j \in \{1,...,n\}$ there exists a vertex in $V_i$ and a vertex in $V_j$ that are not an edge of $G$. Then it ...
user324789's user avatar
5 votes
1 answer
626 views

A graph whose every odd cycle is a triangle is 4-colorable

As the title says, I have a simple finite graph whose every odd cycle is a triangle, and I want to show that $\chi (G)\leq 4$. My idea was trying to use the fact that a graph is bipartite iff it ...
35T41's user avatar
  • 3,387
4 votes
1 answer
1k views

Q: Proving G is d-colorable

I'm studying graph theory, coloring at the moment. I'm stuck with a proof of the following exercise: Let $G = (V, E)$ be a connected graph and let $v \in V$ be such that $deg(v)\lt d$. If $deg(w)\le d$...
VOLTUUH's user avatar
  • 41
4 votes
1 answer
2k views

What is the smallest (in terms of vertices) 5-chromatic $K_5$-free graph?

I am looking for graphs that can be vertex-colored using at least 5 colors, but does not contain $K_5$ (a clique of size 5) as a sub-graph. The question is what is the smallest number of vertices a ...
karp's user avatar
  • 79
4 votes
1 answer
8k views

Let $G$ be a graph with $n$ vertices. Prove that $\chi(G) \ge \frac{n}{\alpha(G)}$

$\chi$ is the chromatic number of $G$, and $\alpha$ is the independence number of $G$. I know that if $G$ has a proper coloring, then the set of vertices with a particular color is an independent set....
Dewick47's user avatar
  • 697
4 votes
2 answers
2k views

Prove that if G is a simple graph, $\chi \geq \frac{|V|^2}{|V|^2-2|E|}$

For a simple graph $G=(V,E)$, I have to prove the following bound on the chromatic number of $G$: $$\chi \geq \frac{|V|^2}{|V|^2-2|E|}$$
Sourav Sarkar's user avatar
3 votes
2 answers
4k 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. ...
ejb11's user avatar
  • 33
3 votes
1 answer
504 views

Schur's theorem and numbers

Can you give a proof for bounds of Schur's numbers $S(r)$? Please suggest me articles to have better idea of Schur's theorem (Ramsey theory).
user685714's user avatar