For questions concerned with graph colorings.

learn more… | top users | synonyms (1)

0
votes
0answers
6 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 ...
0
votes
1answer
19 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
14 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
17 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
35 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
24 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
36 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 ...
0
votes
0answers
24 views

Proving that a sequence is a martingale [closed]

Let $X_i$ be the random variable for the event that the edge $i$ exists in a graph. Note that the maximum number of edges possible = $^nC_2$. And let $\chi$ be the chromatic number of the graph ...
0
votes
1answer
23 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 ...
1
vote
1answer
23 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
7 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
40 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
91 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
53 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 ...
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 ...
1
vote
0answers
96 views

Circumscribed simple line arrangements are 3-colourable?

An arrangement of $s$ lines are drawn in the euclidean plane so that no three lines intersect at a common point and no two lines are parallel. Now circumscribe this arrangement by a circle so that all ...
0
votes
1answer
63 views

Counting edges in a finite connected graph where each vertex is exactly one of two values.

Let $p,q$ and $r$ be positive integers greater than $0$ with $q\neq r$. Suppose that $H$ is a finite connected graph without loops or multiedges on $p$ vertices with $q$ vertices of degree $r$, $r$ ...
0
votes
1answer
26 views

Understanding pairs of odd cycles can 5 colour a graph

Here a proof I am trying to make sense of. Let $G$ be a graph in which each pair of odd cycles shares a common vertex. Show that $\chi(G)\leq 5$. Let $C$ be any odd cycle of $G$ (if none ...
0
votes
1answer
58 views

How many ways to color a graph with 10 colors

Assume that we have ten colors to choose from. Assume that the vertices are distinguishable. How many ways are there to color the following graph? (A coloring of a graph is a painting of the vertices ...
1
vote
1answer
68 views

What is the expected number of of $k$-tuples of vertices such that all edges between the vertices have the same colour?

Consider the complete graph $K_n$ and suppose we colour each edge of $K_n$ red or blue with equal probability. For every $k$, $1\leq k \leq n$, give a formula for the expected number of $k$-tuples ...
0
votes
1answer
21 views

If a graph $G$ has a complete subgraph $K_t$, then the chromatic number $\ge t$

I'm aware of the above theorem -- namely that if a graph G contains a complete subgraph on t vertices, then the chromatic number is AT LEAST t. But, I'm wondering if anyone can show me some example ...
1
vote
2answers
31 views

If you colored every point of a circle 1 of 2 colors, is there always 2 same-colored points of distance $R$ apart?

If every point on a circle of radius $R$ in $\mathbb{R}^{2}$ were colored one of two colors, is there necessarily two points that are of the same color and of distance $R$ apart? what about $>2$ ...
1
vote
0answers
74 views

Is this proof of the four color theorem for infinite graphs legit?

So you got an infinite planar graph $G$. I will prove that it is four colorable. So, construct an infinite number of statements about graphs: The first is "is four colorable" Next, for each vertex ...
1
vote
1answer
30 views

Set Theory: Graphs and $k$-Colorings

Let $G = (V, E)$ be a graph with $V = \omega$. Show that if for all $n < \omega$, the graph $G_{n} = (n, E \cap [n]^{2})$ is $k$-colorable, then $G$ is $k$-colorable. I know how to prove this ...
1
vote
1answer
35 views

Matching numbers and colors

I'm sorry I can't ask this problem in a more formal way, the issue being that I'm not even sure what type of math this involves; I think it actually translate to a graph-coloring problem? FWIW, it's ...
1
vote
1answer
86 views

Coloring/Labelling problem in Polynomial reduction of Isomorphism

** Question :** Notice the inequality inside yellow box. If $i_1$ has $n$ possible vertex, then $j$ has maximum $(n-1)$ vertices. For $\mu_{i_1,j}$ , it should be $1\leq j \leq (n-1)$ . but it is ...
0
votes
1answer
53 views

Example of graph with specific $\chi (G)$, $\omega (G)$, $\beta (G)$

Find an original example of a graph whose chromatic number does not equal its clique number, yet whose clique partition number equals its independence number. Chromatic number: $\chi(G)$ is the ...
0
votes
1answer
28 views

Independence Number Proof Explanation

In the following proof it states that "$v_i$ is less than or equal to the independence number for all $i$." Why is this true? I know what an independence number represents, I am struggling to ...
1
vote
0answers
35 views

Greedy algorithm fails to give chromatic number

Produce a graph and degree sequence for which the greedy algorithm fails to give the chromatic number. My first example is below- The first labeling uses 2 colors which is the chromatic number and ...
1
vote
1answer
36 views

Vertex deletion and chromatic number proof

Let G be a graph such that, for all vertices $a$ and $b$, $\chi(G-${$a-b$}$)=\chi(G)-2$. Prove that G is a complete graph. I started by drawing $K_5$ which has chromatic number $\chi(K_5)=5$ and ...
6
votes
0answers
41 views

Chromatic Number of Circulant Graph

Consider the Circulant Graph $Ci_{2n}(1,n-1,n)$ as described here: http://mathworld.wolfram.com/MusicalGraph.html Another way to describe $Ci_{2n}(1,n-1,n)$ would be $2n$ vertices with vertex set ...
2
votes
1answer
69 views

Does there exist a graph with chromatic number 4 that has no triangle or square cycles?

$K_4$ is an example of a graph that requires 4 colours to be coloured but it contains triangle cycles and a square cycle too. I've tried drawing ever more complicated graphs made up of pentagons, ...
2
votes
2answers
54 views

Number of Labels used in reduction of Isomorphism of Labelled Graph to Graph Isomorphism

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann , Assume that both $X$ and $X'$ have $n$ vertices. We plan to code the graph labels as suitable subgraphs which we attach to the ...
3
votes
1answer
52 views

Prove that a one-color $K_4$ exists in a two-color $K_{18}$

An edge coloring of a graph is an assignment of colors to the edges of the graph. I have $K_{18}$ colored with blue and red and I want to show that it contains a $K_4$ colored with just one color. ...
1
vote
0answers
49 views

Graphs of (un)bounded color valence

Talking about colored graphs there is a definition given for graphs with bounded color valence. This definition is as follows: A vertex-colored graph $G=(V,E)$ has bounded color valence, if there ...
1
vote
1answer
31 views

Show impossibility of a perfect covering

Problem: Show that a $8 \times 8$ chessboard cannot be perfectly covered by $1$ square tetramino, and 15 other tetraminoes chosen from straight tetraminoes and Z-tetraminoes. My attempt: I tried to ...
1
vote
1answer
126 views

How to count the closed left-hand turn paths of planar bicubic graphs?

When you draw a planar cubic bipartite graph $\Gamma$ and 3-color its edges you can use this as an orientation $\mathcal O$. Definition A left-hand turn path on $(\Gamma, \mathcal O)$ is a closed ...
1
vote
1answer
29 views

Inequality with edges and chromatic number.

I have proved the statement : Every graph $G$ with $\chi(g)=k$ has at least $\binom{k}{2}$ edges. I did this my saying for any 2 colours, there exists an edge connecting one vertex of one colour to ...
0
votes
0answers
36 views

Third coefficient of the chromatic polynomial

If G is a graph and $\chi(G,k)=\sum _{i=0} ^{n-1} a_i k^{n-i}$ I know that $a_0 = 1$ and $a_1 = -|E(G)|$ I'm looking for a formula for $a_2$ using |V|, |E| and the number of independent sets of ...
2
votes
1answer
59 views

Chromatic Index in Graph

There is a graph $G$ with maximum degree that is greater than $0$. Suppose that $G$ contains a perfect matching $P$ and that $G-P$ (graph after removing all edges of $P$ in $G$) is bipartite. What is ...
0
votes
0answers
21 views

Deleting any edge leads to a unique Hamiltonian cycle.

The Markström graph has the property that deleting any edge makes the Hamiltonian cycle unique. Other than $K_4$, what other graphs have this property? What is this property called?
0
votes
0answers
46 views

Find the chromatic polynomial of the $3 \times 3$ grid graph

Find the chromatic polynomial of the $3 \times 3$ grid graph. Maple give the answer $$ \lambda\, \left( \lambda-1 \right) \left( {\lambda}^{7}-11\,{\lambda} ...
0
votes
0answers
20 views

Chromatic polynomial of simple graph

Suppose I know the chromatic polynomial $P(G, \lambda)$ of the graph $G$. Can we express the chromatic polynomial of the graph $G'$ in terms of $P(G, \lambda)$ and $\lambda$? I have tried to ...
1
vote
1answer
22 views

Add one edge to the graph such that the graph will not be 3-colourable

Could you guys help me solve this example? The question is, whether it is possible to add one new edge such that the resulting graph is not 3-colourable and prove it. I was trying to find a way to ...
2
votes
1answer
11 views

Add edge such that resulting graph is 2-degenerate

I'm preparing for an exams and I can't find out how to solve this kind of examples. The question is, whether it is possible to add two new edges into the graph such that the resulting graph is ...
1
vote
0answers
42 views

Finding the Chromatic Polynomial for the wheel graph $W_5$

Let $G$ be a graph and let $k \in N$. The chromatic polynomial $P_G(k)$ is the number of distinct $k$-colourings if the vertices of G. Standard results for chromatic polynomials: 1) $G = ...
0
votes
0answers
14 views

Deriving upper bound on number of recolorings of 3-colorable graph that 2-coloring won't give any monochromatic triangle

I clearly don't uderstand something in this exercise (because my answers seems to trivial to me). Let G be a 3-colorable graph. Consider the following algorithm for finding such a 2-coloring. ...
0
votes
1answer
34 views

Is there a graph that cannot be colored by k colors for k greater than its chromatic number? [closed]

Is there a graph that is not proper color-able using exactly k colors where k greater than the chromatic number (and smaller than number of vertices)?
3
votes
0answers
58 views

Automatic solver of four-color theorem? [closed]

Does anyone know of an app/online tool to automatically colour any map or image using the 4-colour theorem? (Taking a Black and white image as input).