For questions concerned with graph colorings.

learn more… | top users | synonyms (1)

0
votes
0answers
4 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
34 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
34 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
99 views
+50

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
52 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
43 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
24 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
37 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
39 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
36 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
20 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
35 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
45 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
55 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
31 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
35 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
15 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
23 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
47 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
96 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
19 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
17 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
31 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
41 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
34 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
51 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
51 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
19 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
18 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
26 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
30 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
32 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
46 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 ...
1
vote
1answer
45 views

Prove that every edge-coloring of $K_{17}$ with $3$ colors contains a monochromatic $K_3$. [duplicate]

Also, Prove that every edge-coloring of $K_6$ with $2$ colors contains at least two monochromatic copies of $K_3.$ I have no idea how to start these problems. What should I do?
1
vote
1answer
54 views

Find the chromatic number of the graph below.

I know the chromatic number can't be 2 because there's a cycle of 5 there. I tried 3 but to no avail. So I assume the answer is 4. But I can't prove that it's four and not three. Can someone help out? ...
0
votes
1answer
30 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....
1
vote
1answer
31 views

How do I prove that the vertex chromatic number of a subgraph is less than that of the original graph?

How do I prove that the vertex chromatic number of a subgraph is less than that of the original graph? Say I have a graph with chromatic number $k$. How do I prove that the chromatic number any ...
0
votes
0answers
9 views

Prove that chromatic number of a graph is less than the chromatic number of its Hajos graph.

Prove that $\chi (G) <= \chi (H (G,v_1,v_2)) <= \chi (G-v_1v_2) + 1$, where $H (G)$ is the Hajos graph of g.
0
votes
1answer
45 views

Clique number of the Hajos Construction of a Graph

Prove that $\omega(G)-1 \leq \omega(H(G,v_1,v_2)) \leq \omega(G) $. The $H(G,v1,v2)$ indicates the Hajos Construction of a graph. I can prove this for $K_n$ but I have no idea how to generalize for ...
4
votes
2answers
99 views

What is a “map” in the four color theorem?

The four color theorem declares that any map in the plane (and, more generally, spheres and so on) can be colored with four colors so that no two adjacent regions have the same colors. However, it's ...
1
vote
0answers
8 views

Cutting a colour-critical indecomposable graph

Let $G=(V,E)$ be an arbitrary indecomposable k-colour-critical graph ($k\geq4$). Is it in general possible to find a cut $C=(S,T)$, such that $S$ is a $k-1$-chromatic graph and $T$ is the complete ...
2
votes
1answer
60 views

$3$-colourings of a complete graph without monochromatic spanning trees

It is not difficult to prove that for every $2$-colouring of the edges of a complete graph, there is a monochromatic spanning tree, based on the fact that a graph or its complement has to be connected....
1
vote
1answer
20 views

Chromatic number of graph obtained by removing set of edges from complete graph

Consider the complete graph on n vertices $S = (V, E)$ and let $K$ be a subset of $E$. If $k$ is the size of the maximal set of independent edges (edges with no common endpoints) in $K$, is the ...