For questions concerned with graph colorings.

learn more… | top users | synonyms (1)

2
votes
2answers
48 views

Vertex Coloring Optimal Sum vs Chromatic Number

I am having trouble coming up with an example of when the number of colors used in the optimal solution of the sum coloring problem of a graph is strictly greater than the chromatic number of that ...
2
votes
1answer
63 views

Chromatic number of graph of subsets of a set [closed]

Suppose set $A$ with $2n$ elements. Construct simple graph $G$ with $\left(\begin{array}{c}2n\\ n\end{array}\right)$ vertices each one represents one of $n$_sized subsets of $A$ .Connect any two ...
0
votes
2answers
14 views

Is there always a minimal coloring for a graph for which one of the colors is a maximum set?

Take a graph $G$ and suppose it is $k$-chromatic. Is there always a $k$-coloring such that one of the "colors" (the independent sets that compose the coloring) will have cardinality equal to $G$'s ...
2
votes
1answer
67 views

Truncated objects coloring

I am looking for ways to color a truncated tetrahedron allowing rotations and reflections. I know the ways to color a tetrahedron in a similar way but stumped on this. From wikipedia, both tetrahedron ...
1
vote
1answer
30 views

Four color theorem for 'solid' maps

Is there an equivalent of the four color theorem for 'solid' maps? In other words, if we consider a 'map' in $3D$ what is the minimum number of colors we have to use in order to avoid that two ...
1
vote
1answer
48 views

Coloring a triangular bipyramid

A triangular bipyramid looks like this: http://mathworld.wolfram.com/TriangularDipyramid.html I have to find the ways to color it using n colors allowing rotations and reflections. I do not ...
2
votes
1answer
29 views

There must be a monochromatic odd cycle in $t$-coloring of $K_{2^t+1}$

Prove: if we $t$-color the edges of the complete graph on $2^t+1$ vertices, then there must be a monochromatic odd cycle. This is supposed to be an easy exercise but I haven't made much progress. ...
7
votes
2answers
189 views

Coloring the pentagonal hexecontahedron

So, I'd like to color the pentagonal hexecontahedron in a way that is satisfying aesthetically and mathematically. For me this equates to, in order of priority - 1. No same-colored faces can share an ...
0
votes
1answer
42 views

Prove there's a monochromatic isosceles triangle.

The points in a circle are coloured red and blue. Prove that there exists a monochromatic isoceles triangle. I can prove that there exists a monochromatic triangle. If there are no three points of ...
-1
votes
0answers
11 views

labeling all edge 2-colorings of the complete graph $K_n$ with binary codes

can we label all edge 2-colorings of the complete graph $K_n$ with binary codes (or Gary codes) so that any monochromatic $K_k$ clique be assigned as a string of ${k\choose 2}$ sub string of ...
1
vote
0answers
16 views

Convex 4-polytopes requiring 6 or more colors

Projected into 3-D space, a convex 4-polytope looks like a collection of convex polyhedra. If any two convex cells sharing a face have different colors, how many colors are required? In the paper ...
1
vote
1answer
35 views

Prove there are two points an integral number of inches apart of the same colour

A line is coloured in $11$ colours. Prove that there are two points of the same colour that are an integral number of inches apart. I don't know how to do this, but I know how to do a similar problem ...
2
votes
0answers
35 views

Graphs derived from colorings of locally finite graphs

Let us assume we are in the following situation: We have a connected regular locally finite graph $G=(V,E)$ and let us call the degree of an arbitrary (and therefore any) vertex $d$. In addition we ...
0
votes
0answers
9 views

Colouring arbitrary regions, in a 2D plane populated with bicolored points

How may I efficiently colour arbitrary regions, according to the majority captured points, in a 2D plane populated with bicolored points distributed according to some unknown distributions. I could ...
3
votes
0answers
127 views

Maximal unit lengths in 3D with $n$ points.

Given $n$ points in 3D space (V), what is the maximal number of unit distance lengths (E) between those points? Here are a few possibilities. Some of them are chromatic spindles. ...
1
vote
1answer
56 views

Find the chromatic polynomial of a graph

My answer: $p(g,k) = k(k-1)^4(k-2)(k-3) $ I'm new to this subject so was hoping if one of you could check my answer. Thanks. Vertices:
0
votes
0answers
50 views

Edge-matching icosahedron puzzle

Color the edges of an icosahedron with 4 colors so that all 20 triangles have a distinct set of colors. Color the edges of an icosahedron with 6 colors so that all 20 triangles have a distinct set ...
1
vote
1answer
26 views

Help understanding the chromatic numbers of the planes upper bound.

I've been studying the Chromtic number of the plane and it shows that a hexagonal tiling of seven colors shows that 7 is an upper bound. I couldn't actually follow the argument that proves this is ...
0
votes
0answers
15 views

$k$-vertex-critical graph which is not $k$-edge-critical

A graph like $G$ is called $k$-vertex-critical if $\chi(G)=k$ and $\forall v\in V(G)\space\chi(G-v)\lt\chi(G)$ where $\chi(G)$ is the vertex chromatic number of $G$. A graph like $G$ is called $k$-...
1
vote
1answer
39 views

Prove : Each distinct $R_{k,e}$ can appear maximum $\sqrt b \leq n^{3}$ times.

Notation: $H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...
2
votes
0answers
40 views

Coloring (W-L Method)

I am trying to read An Optimal Lower Bound on the Number of Variables for Graph Identification. On page 3 (4th paragraph), it is written- It might color vertices and edges implicitly by using $k$-...
1
vote
0answers
15 views

Trying to understand some claims on chromatic number of union of graphs

Let $G_1=(V,E_1)$ and $G_2=(V,E_2)$ be graphs. Let $c_1:V\to[\chi(G_1)]$ and $c_2:V\to[\chi(G_2)]$ be proper colourings of $G_1$ and $G_2$ respectively. My questions: I am trying to understand the ...
3
votes
2answers
39 views

Some (trivial?) doubts on the proof of chromatic number of any planar graph is at most 6

I am trying to show that chromatic number of any planar graph is at most 6. This is a weaker statement of the Four-Colour Theorem. I have a vague idea about the proof but not sure how to convince ...
1
vote
1answer
21 views

Chromatic number of a graph after a vertex is deleted from it.

What happens to the chromatic number of a graph, G, when one of its vertices, v, is deleted? By this I mean what will be the chromatic number of the subgraph G-v? I know that the chromatic number can ...
0
votes
1answer
36 views

Four color theorem and five color theorem

Every graph whose chromatic number is more than ____ is not planner. My attempt: The answer should be $4$ by four color theorem. Somewhere, I read "Five color theorem"(See Theorem 6.3.8 at ...
3
votes
1answer
46 views

Hypergraph $2$-colorability is NP-complete

So far all my searches for a proof of this well-known theorem have led me to the one below (Lovász 1973), reducing $k$-colorability for ordinary graphs to $2$-colorability for hypergraphs. In the ...
0
votes
1answer
56 views

Total Chromatic Number of Cycles

According to Wikipedia, In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be ...
1
vote
1answer
21 views

For every simple graph like $G$ , $\chi(G) \le {(2e)}^{\frac{1}{2}}$

$\chi(G)$ The chromatic number of a graph is the smallest number of colors needed to color the vertices of so that no two adjacent vertices share the same color. Now the question : Assume that $G$ ...
0
votes
1answer
33 views

Upper bound on the list chromatic number of $d$-degenerate graphs

It can be proved that $\chi(G)\le d+1$ if $G$ is $d$-degenerate, but can we also say that $\chi_\ell(G)\le d+1$, in general[note 1]? Here, $\chi(G)$ is the chromatic number of $G$ and $\chi_\ell(G)$ ...
1
vote
1answer
37 views

A graph with list chromatic number $4$ and chromatic number $3$

What is an example of a graph with chromatic number $\chi(G)=3$ and list-chromatic number $\chi_\ell(G)=4$? My first thought was to consider complete tripartite graphs since these will have chromatic ...
0
votes
0answers
16 views

Covering $10 \times 10$ board with L tetromino

Is it possible to cover a $10 \times 10$ board using L- tetrominoes? I think the problem relates to coloring proof but can't find a suitable colouring. Any help is greatly appreciated. P.S. Can ...
1
vote
0answers
25 views

forbidden chromatic polynomial

We wish to show below chromatic polynomial are not exist; It means that we couldn't find any graph that has one of these chromatic polynomial 1- $\ k^5 - 4k^4 + 8k^3 - 4k^2 +k$ 2- $\ k^4 - 3k^3 + k^...
0
votes
2answers
49 views

Show that if any two odd cycles of G have a vertex in common, then $\chi(G)$ <= 5 [closed]

A vertex coloring is an assignment of labels or colors to each vertex of a graph such that no edge connects two identically colored vertices. The most common type of vertex coloring seeks to minimize ...
4
votes
2answers
100 views

Reducing a graph without lowering its chromatic number

While trying to find an algorithm to reduce a graph without lowering its chromatic number, I made the following algorithm (but not sure if it works): Given a (simple) graph $G$, look for subgraphs ...
2
votes
2answers
20 views

Monochromatic congruent triangles on a 10-gon

Five vertices of a regular $10$-gon are painted red and five blue. Prove that there will always be two congruent monochromatic triangles. Please tell me if my proof is acceptable. I don't know how ...
0
votes
1answer
32 views

Let $G$ be a graph such that $\chi(G - x - y) = \chi(G) - 2$, for all distinct vertices $x,y$. Prove that $G$ is complete.

I understand that it's a complete graph because $\chi(K_n) = n$ (by Brooks theorem), so when we start cutting vertices, with $K_{n-1}$ we will have $\chi(K_{n-1}) = n-1$. My question is how would I ...
0
votes
0answers
19 views

Edge Chromatic Number of Product Graphs

Assume that two graphs like $G$ and $H$ are given. $G \times H$ is a graph such that every vertex of it comes from $V(G) \times V(H)$ and every vertex like $(u,v)$ is adjacent to $(u',v')$ iff : $1$...
1
vote
1answer
33 views

An algorithm for proper edge-coloring of every simple graph with $\delta+1$ colors

A proper $k$-edge-coloring for a graph like $G$ is coloring every $e \in E(G)$ with $k$ colors such that no two edges of the same color share a common vertex. According to Vizing Theorem, for every ...
0
votes
1answer
42 views

An example of a vertex-critical graph which is not edge-critial

$\chi(G)$ ( vertex-chromatic number of a graph like $G$) is the minimum number of colors which is enough to color every vertex of $G$ such that no two adjacent vertices have the same color. A graph ...
1
vote
1answer
35 views

Vertices coloring in Combinatorics

For graph $A$ and $B$, define $A \times B$ to have vertex set $V(A) \times V(B)$, with $(a,b)$ adjacent to $(c,d)$ if $a$ is joined to $c$ in $A$, $b$ is joined to $d$ in $B$(assume they are not the ...
2
votes
0answers
54 views

Chromatic Number and Odd Cycles

It's a well known fact that a graph is bipartite if and only if it contains no odd cycles. This is an interesting generalization: Call a sub-graph nice if it has an odd number of vertices (more than ...
2
votes
2answers
52 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|}$$
2
votes
1answer
37 views

How to create some large 3-regular planar graphs

I'm looking for a way to produce very large (100-2000 vertices) 3-regular planar graphs. I've tried to use plantri (plantri -m5 -v 100), but I was not able to produce only random examples (10-50 ...
1
vote
1answer
60 views

Are $6$ hotels enough to separate $n$ mathematicians?

A convention of mathematicians will have rooms available in $6$ hotels. There are $n$ mathematicians and, because of personality conflicts, various pairs of mathematicians must be lodged in different ...
0
votes
1answer
22 views

An example of vertex transitive graph whose chromatic number and clique number is apart.

Can someone give me an example of graph have the following property? must have: the chromatic number and clique number differ more than 2, the more the better. better have: the fewer size the ...
0
votes
0answers
23 views

2COL to 2SAT clausal form

Consider the instance of lableled-2-COL given by the graph below: We can convert this problem to 2-SAT in clausal form: A hint in the question required that the first two clauses were $$(a,b),(\...
0
votes
1answer
27 views

If $G$ is a graph with $2k+1$ vertices and $|E(G)| \gt k\Delta(G)$ , then $ \chi'(G) \ge \Delta(G)+1$

We define : $\chi'(G)$ is the minimum number of colors we need in order to color all edges of the graph $G$. Assume that we have a graph like $G$ with $2k+1$ vertices and $|E(G)| \gt k\Delta(G)$. ...
1
vote
1answer
33 views

Prove that every triangle-free graph on n vertices has chromatic number at most 2√n.

How do I start the proof? Do I start by creating any triangle free graph or is there a theorem that I need to use?
0
votes
1answer
33 views

How to draw K1,3 and C5 as a cartesian product?

I've already drawn a complete bipartite graph with 1 vertex in the 'X' set and 3 vertices in the 'Y' set, but how do I fit the C5 in that graph? I can't picture it. Then how do I find the maximum ...
1
vote
1answer
48 views

Coloring problem with equilateral triangles

Prove: If we color the plain with three different colours, then there will always be an equilateral triangle which has three vertices of the same colour. I have proved it for two colours but I just ...