For questions concerned with graph colorings.

learn more… | top users | synonyms (1)

1
vote
1answer
8 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
25 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
35 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, ...
1
vote
1answer
26 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
45 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
36 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
29 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 ...
0
votes
0answers
71 views
+50

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
19 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
27 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
46 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
19 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
41 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
18 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
14 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
25 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
7 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
33 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)?
0
votes
0answers
19 views

Is the number of vertex-face colorings of a planar graph encoded in the Tutte polynomial?

A vertex-face coloring of a planar graph is where one simultaneously colors vertices and faces of the graph so no two adjacent vertices have the same color; no two adjacent faces have the same ...
5
votes
1answer
63 views

in every coloring $1,…,n$ there are distinct integers $a,b,c,d$ such that $a+b+c=d$

Prove that for every $k$ there is a finite integer $n = n(k)$ so that for any coloring of the integers $1, 2, . . . , n$ by $k$ colors there are distinct integers $a, b, c$ and $d$ of the same color ...
0
votes
0answers
30 views

Partition graph's edges into $k+1$ pairwise disjoint sets

Let $G = (V, E)$ be a (simple) graph with maximum degree $k \gt 1$ and exactly $k(k + 1)$ edges. Prove that the set of edges of $G$ can be partitioned into $k + 1$ pairwise disjoint sets, each forming ...
1
vote
2answers
75 views

Example of non-commutative association scheme

I need an example of non-commutative association scheme of ordered 6. I tried to use the example in the book Handbook of Combinatorial Designs, Second Edition by Charles J. Colbourn‏،Jeffrey H. Dini ...
3
votes
2answers
50 views

prove that for any $k$-regular graph $G$, $\chi(G) \geq \frac n{n-k}$

This question is a part of another question that has two sections. In the first section I proved that for any graph $G$, $\frac n{\alpha(G)} \leq \chi(G)$ and $\chi(G) \leq n-\alpha(G)+1$. Now I ...
1
vote
2answers
41 views

Number of ways to color n objects with 3 colors if colors must be used once

I am aware this combinatoric problem (which I got from Discrete Mathematics Elementary and Beyond) has been answered on here before, but from what I can tell the solution I have come up with is ...
4
votes
1answer
35 views

Simplest algorithm for edge coloring of a dodecahedron?

I have an origami model of a dodecahedron I am assembling. There are 30 edges with 3 colors of 10 each. I could use a diagram that gives a possible 3 color edge coloring. However, is there some sort ...
0
votes
2answers
28 views

How can I prove ($number \ of\ verticies \over size \ of\ maximum\ independent \ set$ ) $\leq$ chromatic number?

How can I prove $$n/ \beta(G) \leq \chi(G)$$ . I thought of using an algorithm that selects a maximum independent set and gives them a color and etc. but this does not necessarily give a minimum ...
2
votes
1answer
66 views

Coloring diagonals in a regular polygon

Each side and diagonal of a regular $n$-gon ($n\geq 3$) is colored blue or green. A move consists of choosing a vertex and switching the color of each segment incident to that vertex (from blue to ...
2
votes
1answer
33 views

Total chromatic number of complete bipartite graph

Does anybody know the total chromatic number of the complete bipartite graph $K_{m,n}$? I've searched for it and I find some assertion that it is sometimes $\Delta(K_{m,n})+1$ and sometimes ...
1
vote
2answers
55 views

Graph theory, graph coloring, hamilton

A simple graph G has $14$ vertices and $85$ edges. Show that G must have a Hamilton circuit but does not have an Euler circuit. My attempt: to be hamilton circuit, each should have degree at least ...
5
votes
2answers
67 views

Weird Coloring Problem [duplicate]

I'm having some issues reasoning through a particular problem. Consider a problem where I color all points in $\mathbb{R}^3$ with the colors red, green, blue. I want to show that every positive real ...
0
votes
0answers
27 views

Chromatic number of random graph

Building random graph with probability to connect two vertex $p = \frac{1}{2n}$, and not connect $q = 1 - \frac{1}{2n}$. Find chromatic number a.a.s.(asymptotically almost shure), when $n$ tends to ...
3
votes
1answer
37 views

Every bridgless planar 3-regular graph is 3-edge colorable

How to prove an implication Every bridgless planar 3-regular graph G is 3-edge colorable. I know: From Vizing Theorem, that I can color G with 3 or 4 colors. I have a hint to use that we have ...
0
votes
0answers
19 views

The least edges to ensure the graph is still connected after removing edges of any two colours.

Use k colours to paint edges of a undirected graph of n nodes. Each edge has one colour. What is the number of the least edges to ensure the graph is still connected after removing all edges of any ...
1
vote
1answer
25 views

Scheduling problem on bipartite graph

Consider a bipartite graph $(G, U, V)$. Each $v$ in $V$ represents a soccer team, and each $u$ in $U$ represents a mini-tournament needs to be scheduled. If $u_i$ and $u_j$ share no common neighbor, ...
2
votes
1answer
56 views

Chromatic number of Queen tour

On a regular chess board, let every square represent a vertex. Then, two vertices are connected iff a queen can travel from one square to another in one move (directly). I'm trying to calculate the ...
2
votes
2answers
28 views

Are there any vertex colouring algorithms which colour regular graphs optimally?

As the question suggests I am looking for a vertex colouring algorithm preferably exact, which can colour regular graphs optimally. Is there any which is known in literature?
0
votes
1answer
30 views

Chromatic number of a graph on a binary alphabet

given the graph defined in this post: A binary sequence graph i.e., Define a graph $H(n,2)$ as follows. Each vertex corresponds to a length nn binary sequence and two vertices are adjacent if and ...
0
votes
1answer
26 views

prove that for any graph X(G') is equal or more than $\alpha(G)$

an independent set of G is a subset of V(G) in which no one of that vertices are connected to each other. we define $\alpha(G)$ as maximum size of an independent set of graph G. and also we define ...
0
votes
1answer
52 views

2 color theorem proof, straight lines inside a box

How can I prove mathematically that a box with $x$ straight lines drawn through it, can be colored with only 2 colors.
0
votes
0answers
7 views

Minimize Non Mutual Friend subgroups

If I am given $n$ people and that each person has no more than $x$ friends, what is the minimum number of sub-groups I need to create to ensure that each person in a sub-group contains all mutual ...
1
vote
1answer
23 views

finding maximum matching of a graph from an optimal proper coloring of complement of graph

Let $G:=(V,E)$ be a simple undirected graph. Let $\bar{G}$ denote the complement of $G$. Let $c:V\rightarrow \{1,2,...,\chi(\bar{G})\}$ be a proper coloring of $\bar{G}$. It is clear that the sets of ...
2
votes
1answer
45 views

Find maximal clique in an multigraph with $n$ vertices, where each vertex is colored with $k$ colors.

You are given a multigraph with $n$ vertices. Every vertex is colored with maximum of $k$ colors. If two vertices share a color, there is an edge between them which is colored with that color. (A pair ...
0
votes
1answer
38 views

Proving that $ \chi(G) = \omega(G) $ if $ \bar{G} $ is bipartite.

I know that $ \chi \! \left( \bar{G} \right) = 2 $ and that $ \chi(G) \geq \alpha \! \left( \bar{G} \right) $, but how can I conclude that $ \chi(G) = \omega(G) $?
2
votes
2answers
14 views

Prove Graph G is in Vizing Class 2 if $\alpha$'(G) < |e(G)|/$\Delta$(G)

G is a simple graph with e edges, maximum vertex degree $\Delta$ and edge independence number $\alpha$' which satisfies $\alpha$' < e/$\Delta$. What does this inequality mean? How is it helpful in ...
0
votes
1answer
155 views

Upper bound for chromatic number related to number of edges [closed]

Prove that in any simple, undirected graph $G=(V,E)$, the chromatic number $χ(G)≤ \sqrt{2m} +1$, where $m=|E|$
1
vote
1answer
26 views

Prove that there is a red triangle or a blue triangle that is is a sub-graph

If the edges of $K_6$ are coloured blue or red, prove that there is a red triangle or a blue triangle that is a sub-graph. Well I am having a hard time proving this, I try to prove it by ...
1
vote
1answer
34 views

How can I prove that if $S$ any independent set of $G$ and $G$ is color critical then $ \chi(G−S)=\chi(G)−1$

Let $G$ be a color critical graph and $S$ any independent set of $G$ then $\chi(G−S)=\chi(G)−1.$ I tried to show that any independent set induce one color, but I cannot match it with the color ...
0
votes
1answer
19 views

Can a certain board be covered in Tetrominoes

Prove that a $15x8$ board cannot be covered by $2$ L-tetrominoes and $28$ skew tetrominoes. This is a coloring proof and I have tried a variety of colorings, from stripe colorings to other unique ...
0
votes
1answer
32 views

Non-adjacent vertices have different colour? [closed]

In a proper vertex coloured graph, can two non-adjacent vertices have different colours?