# Tagged Questions

For questions concerned with graph colorings.

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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:
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 ...
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 ...
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$-...
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)}$ ...
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$-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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)$ ...
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 ...
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 ...
25 views

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?