Questions tagged [coloring]
For questions concerned with graph colorings. (This is not for mathematical art.)
1,557
questions
2
votes
1
answer
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 ...
- 77
4
votes
1
answer
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 ...
- 143
3
votes
1
answer
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?
...
- 47
0
votes
1
answer
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 ...
- 13
4
votes
2
answers
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 ...
- 221
1
vote
1
answer
34
views
Why if $\chi (G)=k$, then we have $S(G,k)=\frac{P(G,k)}{k!}$?
Let $G$ be a finite graph of order $n$. Chromatic polynomial of $G$ is defined by $$P(G,\lambda )=\sum_{k=\chi (G)}^{n}S(G,k)(\lambda)_k $$ where $\chi (G)$ is the chromatic number of $G$ and $$(\...
- 351
0
votes
1
answer
34
views
no of different ways to colour vertices of square using one or more colours from the set {R,G,B,Y} such no two adjacent vertices have the same colour
If have to find The number of different ways to colour the vertices of a square PQRS using one or more colours from the set {R,G,B,Y}, such that no two adjacent vertices have the same colour is?
So ...
0
votes
0
answers
29
views
Proof that the graph is the sum of three edge-disjoint bipartite graphs
Question from an old exam:
Let $ G $ be a graph with a chromatic number $ \chi(G) \leq 8 $. Prove that $ G $ is the sum of three edge-disjoint bipartite graphs.
I tried interpreting each of eight ...
- 371
0
votes
0
answers
37
views
Given a fixed set of colors, what is the maximum number of vertices that can be colored?
The chromatic number $\chi(G)$ of a graph $G$ is the smallest number of colors needed to color the vertices of $G$ so that no two adjacent vertices share the same color.
I'm not certain if the ...
- 1,978
1
vote
1
answer
31
views
Edge colouring distinguishing by sums for a complete graph
Let $G=(V_G,E_G)$ will be a simple graph and $f:E\to\{1,...,k\}$ will be edge $k-$coloring. Denote $\sigma_f(x) = \sum_{xy\in E_G}f(xy)$ for $x \in V_G$ Consider a parameter $s(G) = \min\{k:\exists k-\...
- 165
1
vote
1
answer
39
views
Algorithm for Identifying Consistently Colored Node Subsets in Near-Optimal Graph Colorings
I am currently working on a problem related to graph coloring and subset identification. Given an undirected graph, I am interested in finding subsets of nodes that exhibit a consistent coloring ...
- 256
2
votes
1
answer
85
views
How can we theoretically prove that the chromatic number of the graph is 5?
It's easy for us to determine the chromatic number of the graph below as $5$ using a computer program. However, I'm struggling to find a theoretical explanation.
Since the chromatic number of a graph ...
- 1,978
1
vote
1
answer
28
views
Chromatic polynomial by contraction deletion
Consider the graph $G$ with $5$ vertices labelled $1,\cdots,5$ with edges $(12)$,$(13)$, $(23)$, $(34)$ and $(45)$ which means we have a triangle $(123)$ and two other edges $(34)$ and $(45)$. I want ...
- 10.8k
0
votes
0
answers
42
views
In how many different ways the vertices of a tree can be colored using $3$ colors? I need to verify my answer
Let $T = (V, E)$ be a tree with a set of vertices $V = [7]$ and a set of edges:
$$E = \{1, 2 \}, \{1, 3 \}, \{1, 4 \}, \{2, 5 \}, \{3, 6 \}, \{4, 7 \}$$
In how many significantly different ways (with ...
- 1,047
0
votes
1
answer
68
views
Doubt verification regarding tiling.
Question: Is it possible to cover a 10 × 10 board with the (3+1) type L-tetrominoes without them overlapping?
Sol: Color the columns white and black alternatingly. There are 50 white squares and 50 ...
- 49
1
vote
1
answer
53
views
Polynomial Growth Observed in a New Graph Coloring Algorithm: Insight or Oversight?
Hello MathExchange community,
I have developed a graph coloring algorithm that has demonstrated impressive results in initial tests. However, before drawing any concrete conclusions, I'm looking for ...
0
votes
1
answer
64
views
Edges of a complete graph have one of $2$ colors. Prove that every two vertices can be connected by a path of edges of same color of length at most 3.
All edges of a complete graph are colored: each edge with a red or blue color. I need to prove that there exists a color (one of those two) such that every two vertices can be connected by a path with ...
- 1,047
0
votes
1
answer
118
views
Four Color Theorem Disproof Attempt
I was wondering, where I made a mistake in this attempt to disprove the four color map theorem. I hope that you smart folks can help me out.
I already apologize, if the tags are wrong. I am not really ...
user1208304
0
votes
0
answers
37
views
Redfield-Polya enumeration, but the colors don't matter
Is there a version of Redfield-Polya enumeration with the added condition that you don't care which color is which? An illustrative example is: Count edge-colorings of $K_4$ modulo the group action of ...
- 124
2
votes
1
answer
33
views
Large chromatic number implies a clique (weakened Hadwiger's conjecture)
This is an exercise from chapter 7 of Diestel's 'Graph theory':
Show that there exists a function $f$ such that each graph $G$ of chromatic number at least $f(r)$ contains a $K_r$ minor.
My attempts ...
- 355
0
votes
0
answers
33
views
If 3 colours are used for a plane there exists a length 1 segment with edges of same colour.
A secondary school problem:
Prove that for any colouring of a plane with three colours there exists a segment of length 1 with edges of same colour.
My attempt to prove. Take any point A on the plane ...
- 797
0
votes
1
answer
71
views
Why can't two colors disconnect a complete graph?
As how concise the title is, my question is: why can't two colors disconnect a complete graph?
This problem originates from this codeforces problem: Train splitting, which roughly translates as "...
4
votes
1
answer
243
views
Is there an exponential lower bound for the chromatic number?
Let $n$ be a positive integer. Define the Hamming distance $d_H(x,y)$ of $x,y\in\{0,1\}^n$ by $$d_H(x,y)=|\big\{i\in\{0,\ldots,n-1\}:x(i)\neq y(i)\big\}|.$$
For integers $n>1$ and $k$ with $1\leq k&...
- 237
0
votes
1
answer
36
views
Finding the Chromatic Polynomial for a given graph.
triangle graph with one chord inside from the top to the base and the base is extended to one node outside on the left
I have this question in a sample paper. I am not able to figure out how to find ...
0
votes
1
answer
18
views
Chromatic number of hypergraph given rank and maximum degree
Lemma 4.3 of the following paper https://faculty.math.illinois.edu/~z-furedi/PUBS/furedi_kahn_poset-dimension.pdf states that a hypergraph with rank a and maximum degree b can be colored with (a-1)b+1 ...
- 1
1
vote
0
answers
30
views
Is it always possible to create a minimum depth tree where tree nodes are unique and have a 'choice'?
This is a somewhat long question thus sincere apologies beforehand. In a tree a node is a simple point. Now instead of a node let us consider a set of 'choice nodes' that have the following properties:...
- 141
0
votes
0
answers
37
views
A graph coloring game of merging subgraphs
A graph coloring game
This is a 2-player game played by players $A$ and $B$. A random non-trivial planar connected graph $G(V,E)$ is chosen. Player $A$ sets up the game as follows:
Player $A$ ...
- 3,133
1
vote
0
answers
33
views
counterexample to 4-color theorem must contain no separating 4-cycle
In Graph Theory by Bondy and Murty, on page 397, the following is left as an exercise (to prove both of them):
($G$ is a minimal counterexample to the 4-color theorem)
Theorem: $G$ contains no ...
1
vote
0
answers
87
views
number of green and red edge colorings on a complete graph such that there's at least one triangle with $2$ green sides and $1$ red side
Problem Description
Let $K_n$ be a complete graph on $n \ge 3$ labelled vertices $v_1, v_2, ..., v_n$. If every edge must be colored either green or red, then how many $N$ distinct ways can the edges ...
- 4,604
3
votes
1
answer
125
views
Does an island need five colors, if there is a unique color assigned to the sea?
Suppose you specify that the sea must be a royal blue, and no land territory is allowed to be. Does the map then need five colors? Or can the island necessarily be colored with three (non-royal blue) ...
- 229
0
votes
0
answers
51
views
Can the Four Colour Theorem be proved using Albertson's Conjecture?
The Albertson's conjecture states that:
Among all graphs requiring $n$ colors, the complete graph $K_{n}$ is the one with the smallest crossing number. (I've taken the definition from Wikipedia)
I've ...
- 39
0
votes
0
answers
24
views
Colouring the Marbles around the Circle
Let us say, we have an integer $n$ that satisfies $n \geq 3$. An integer $m \geq n + 1 $ is called n-colourful if, given infinitely
many marbles in each of $n$ colours $C_1, C_2, \dots , C_n$, it is ...
2
votes
1
answer
204
views
4-color coloring game.
Similar to this question.
5-color coloring game.
Let there be two players, $𝐴$ and $𝐵$, and a map.
They now play a game such that:
Player $𝐴$ picks a region and player $𝐵$ colors it such that the ...
- 796
4
votes
1
answer
125
views
Find the maximum value of $\chi(G)$ on all simple graphs $G$ with $30$ nodes and a girth of at least $6$.
Problem statement:
Let $k$ be the maximum value of $\chi(G)$ on all $30$ nodes graphs with a girth of at least $6$. Find two numbers $a$ and $b$ such that $a \leq \chi(G) \leq b$ and $b - a \leq 1$.
...
- 142
1
vote
1
answer
71
views
Every 4-regular connected simple graph edges can be colored with 2 colors so each vertex has 2 edges of each color, why my prove isn't working?
I've tried the following proof, but my professor said it's wrong and didn't explain why but told me "you can't do induction this way", can someone elaborate on his behalf?
Let $G=(V,E)$ .We'...
- 23
0
votes
0
answers
54
views
Polya's enumeration theorem for edge and vertex coloring combined.
Let's say we have a tetrahedron labelled as such:
We want to find the number of distinct ways to color the vertices and edges, such that 2 vertices are green, 2 vertices are red, 4 edges are black ...
1
vote
2
answers
62
views
Coloring of $K_n$ with red and blue st. each vertex is incident with $\frac{n-1}{2}$ blue edges
Let $n=1$ (mod 4). Prove that there is a coloring of the edges of $K_n$ with two colors (say red and blue) such that each vertex is incident with exactly $\frac{n-1}{2}$ blue edges.
I know that I need ...
- 157
0
votes
0
answers
37
views
a formula of fractional edge chromatic number
Given a graph $G$, for a vertex subset $U$, let $t(U)=\frac{2|E(G[U])|}{|U|-1}$.
One (Theorem 4.2.1 of the book "Fractional hypergraph coloring") claims that the fractional edge chromatic ...
- 1,821
3
votes
3
answers
102
views
Coloring the faces of n^3 unit cubes s.t., for each color j between 1 and n, the cubes can be arranged to form nxnxn cube with j-colored outer faces
I encountered the following problem in Paul Zeitz's The Art and Craft of Problem Solving (problem 2.4.16 on page 56 of third edition):
Is it possible to color the faces of 27 identical $1 \times 1 \...
- 137
1
vote
0
answers
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 ...
- 286
0
votes
0
answers
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 ...
- 3
-3
votes
1
answer
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
- 11
0
votes
0
answers
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 ...
- 8,148
4
votes
1
answer
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?...
- 10.7k
1
vote
0
answers
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,...
- 43
0
votes
0
answers
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 ...
- 43
0
votes
1
answer
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 ...
- 57
0
votes
1
answer
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-...
- 168
2
votes
1
answer
35
views
Proving possibilities of building bipartite 2 colored graphs with n vertices
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 ...
- 43
2
votes
0
answers
67
views
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$ ...
