Questions tagged [coloring]

For questions concerned with graph colorings.

Filter by
Sorted by
Tagged with
-4
votes
0answers
19 views

Chromatic Polynomial and Chromatic Number of this graph [closed]

Determine the chromatic polynomial for the following graph and deduce the chromatic number:
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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!
1
vote
1answer
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). ...
-5
votes
0answers
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
-2
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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'...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
0answers
66 views

Greedy Algorithm for planar graphs

Consider the following coloring algorithm for planar graphs: Create a stack $S$ with the vertices of $G$ as follows: (a) If $v$ is has the lowest degree vertex in $G$, add $v$ to $S$ and change to $...
-2
votes
0answers
27 views
2
votes
0answers
22 views

Integer matrix behind a chromatic polynomial?

Any finite graph has a chromatic polynomial, whose value at $n$ is the number of colorings using $n$ different colors. Its polynomiality can be proven by induction. What intrigues me more is its ...
1
vote
1answer
79 views

chromatic number of 2 graphs

The join $G$ + $H$ is critical if and only if both $G$ and $H$ are critical I know that $\chi(G+H)$ = $\chi(G)$ + $\chi(H)$ and since $G$ and $H$ are critical if we remove a vertex from $G$ or $H$ ...
2
votes
0answers
55 views

Problem showing that $\chi(G) \le 3$ constructing $G$ from a finite set of lines and maybe using greedy algorithm

Consider a set of lines in the plane such that there are not three that intersect at the same point, and construct a graph $G$ whose vertices are the intersections of the lines, and where two vertices ...
1
vote
1answer
54 views

Problem for showing a $k$-coloration of the graph $G$

Let $G$ be a $k$-chromatic graph and $$f: V (G) → [k]$$ a $k$-coloration of $G$. Show that for each $i ∈ [1 ,. . . , k]$, there exists u ∈ $f^-1$[i] such that for each $j ∈ [1 ,. . . , k] / [i]$, ...
0
votes
0answers
32 views

Chromatic Number of $S_2$

What is the largest chromatic number of all the graphs $G$ that can be embedded on $S_2$ (the double torus)? To which graph is it associated?
0
votes
0answers
24 views

The Beauty in Heawood Map-Colouring Theorem

Why is the Heawood Map-Colouring Theorem which provides the chromatic number of a graph with genus g important? Why is it necessary? Why is it considered as beautiful and worthwile? Thank you!
0
votes
1answer
32 views

What is the chromatic number of S2?

How can one find the chromatic number of the orientable surface S2 (the double-torus)? Does anyone know of an example which shows this chromatic number by giving an upper bound and a lower bound? ...
3
votes
1answer
64 views

planar graph and its complement

Prove that there is no 9-vertex planar graph $G$, such that the chromatic polynomial of $G$ is equal to the chromatic polynomial of $\overline{G}$. > The chromatic polynomial of graphs is defined ...
2
votes
3answers
58 views

If $G$ has two $k$-colorable subgraphics then $G$ is $k$-colorable

Let $G$ be a graph such that $V (G)$ = $X∪Y$ and there are at most $k - 1$ XY-edges. Suppose the sub-graph generated by $X$ is $k$-colorable by vertices, and the sub-graph generated by $Y$ is also $k$-...
1
vote
1answer
49 views

Chromatic polynomial of planar graphs

The chromatic polynomial of a graph counts the number of its (proper) vertex k-colorings. (more details here) Draw a planar graph $G$ with the maximum number of vertices such that the chromatic ...
1
vote
1answer
43 views

Prove that χ(G+H) = χ(G) + χ(H). (Prove that the chromatic number of G and H is equal to the chromatic number of the joint graph G+H)

Let G and H be two graphs. Prove that χ (G+H) = χ(G) + χ(H), where χ(G) represents the chromatic number of G and χ(H) represents the chromatic number of H, and χ(G+H) is the join of the two graphs....
0
votes
0answers
9 views

Any book on colour harmony with mathematical approach?

I don't know if maths is frequently used for color harmony, but I have seem in a number number articles, And I honestly believe it can be very useful. Please suggest some color theory/harmony book ...
1
vote
1answer
60 views

Every graph $G$ contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set in $G$

Note: So that there is no confusion: with maximal independent set, I do not mean the maximum independent set in $G$. A maximal independent set $I$, is an independent set, which cannot be extended by ...
1
vote
0answers
24 views

Property of $ k $-degenerate graph

An undirected graph is $ k $-degenerate if every subgraph has a vertex of degree at most $ k $. I am trying to prove two properties of $ k $-degenerate graphs. 1) If the average degree of $ G $ is at ...
1
vote
0answers
10 views

Open tools for finding K-cliques in a given graph

I've been trying to calculate some known bounds on Ramsey Numbers through different means, and I kind of fell in love with Kalbfleisch's Construction of Special Edge-Chromatic Graphs (1965). One of ...
2
votes
1answer
45 views

The chromatic number of the cycle graph $C_n$ is $2$ if $n$ is even and $3$ if $n$ is odd. A proof attempt

The following theorem is well known. However, I am trying to get better at proofs in graph theory, so I use every opportunity to practice. I would be very happy about verifications and/or any ...
0
votes
0answers
11 views

How does the (g-b)/(max-min) part of hue calculation works?

Im trying to learn how the convertion of RGB to HSV colors is working in detail. My problem is that i cannot find a good explanation of how the hue calculation works... H : ((r-g)/(max-min) + 1 ) * ...
1
vote
1answer
47 views

color 6 vertical stripes with 4 colors— adjacent stripes different colors BUT use ALL 4 colors

color 6 vertical stripes with 4 colors-- i) adjacent stripes must have different colors ii) use ALL 4 colors the 1st part of the question has been asked before (Flag making with 6 vertical ...
0
votes
0answers
35 views

5-color coloring game.

Lets say there are 2 players, A and B. Lets say we have map. The game is played this way, Player A picks a region, PLayer B colours it in such that the region is a different colour to all adjacent ...
2
votes
2answers
61 views

Graph colouring with non contiguous countries.

I have a map containing a number of countries. Each country is made up of a maximum of $2$ non-contiguous sections (e.g. Mainland US and Alaska). What is the maximum number of colours that will be ...
2
votes
2answers
28 views

Question about number of non equivalent colourings of corners of a regular tetrahedron with k colours

Due to Covid -19 , in our university quizzes are held online and it's hard to ask questions. 3 Days back in my Combinatorics quiz this question was asked on which I am struck. I couldn't solve it in ...
2
votes
1answer
44 views

Non equivalent colourings of regular hexagon( Brualdi Chapter-14 , Exercise -32)

I have a question in this exercise of Richard Brualdi's Introductory Combinatorics. Exercise is -> Determine the number of non equivalent colourings of corners of regular hexagon with colours red, ...
3
votes
2answers
55 views

Every graph has an edge 2-coloring…

Prove that if G is a connected graph that is not an odd cycle, then it has an edge 2-coloring such that every vertex with degree at least two is adjacent to edges of both colors. My own idea was to ...
2
votes
1answer
41 views

Coloring a $(1\times n)$-grid - Did I count correctly?

Q: Given a row of $n$-squares, i.e $(1\times n)$-grid and a set of $N$ distinct colors, including Blue, Green and Black. In how many ways can the grid be colored such that no color is used twice? no ...
0
votes
0answers
26 views

Grundy Coloring Algorithm

I am working on the graph coloring problem: Let $v$ be a vertex of a graph, let $c:V\rightarrow \{1,2,...,k\}$ be the set of colors available for this graph, $N(v)$ the set of neighbors of $v$ and $d(...
1
vote
2answers
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 ...
2
votes
1answer
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$?
0
votes
0answers
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 ...
1
vote
1answer
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.
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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.
0
votes
0answers
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 (...
0
votes
1answer
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?
4
votes
1answer
46 views

Coloring And combinatorics

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 ...
1
vote
1answer
53 views

Graph coloring algorithm's complexity

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 ...

1
2 3 4 5
22