For questions concerned with graph colorings.

learn more… | top users | synonyms (1)

1
vote
1answer
23 views

Is it possible to estimate the number of primes between 0 and a 128 bit number?

I'm attempting to visualize an RSA public/private key pair, or a SHA2 hash. In order to reduce that massive number that is meaningful to humans I'm looking at this SHA2 visualization function to ...
0
votes
0answers
33 views

Graph Coloring and Complete Graph

If a graph is k-colorable, then does it imply that it must have a k-complete graph as it's subgraph? For example if a graph has chromatic no = 5, then is this sufficient to imply that it must have K5 ...
0
votes
0answers
10 views

Hajos construction on C4

I've been asked to prove that χ(H(G, v1, v2)) = χ(G) where H(G,v1,v2) is the Hajós construction of G. However, if I understand the Hajós construction as it's described on wikipedia, then H(C4,v1,v2) ...
0
votes
0answers
14 views

Optimal algorithm for finding maximum number of alternating cycles in edge-colored multigraph

I'm having trouble finding any information on this. Suppose you have an edge-colored multigraph $G$ with its edges being of two colors (for example, a given edge can be either black or grey). An ...
0
votes
1answer
42 views

Combinatorics (coloring)

I know how to solve the two individual problems (lines alone and circles alone) but not combined.
0
votes
1answer
35 views

Vertex cover of size k, prove this graph is (k+1)-colorable

Let G be a graph that has a vertex cover of size l. Prove that G is (l+1)-colorable. This is supposed to be true. But I'm confused since a vertex cover can be the cover of the entire graph G. So then ...
0
votes
1answer
15 views

Polya-Burnside coloring question of regular n-gon, detailed explanation

Say I have a pentagon and I want to color each of its vertices using 2 colors. To apply Burnside theorem, I am letting the dihedral group $D_{10n}$ act and there's a hint saying assign symmetry to ...
0
votes
1answer
15 views

Examples of coloring algorithms

I searched for graph coloring algorithms in google, but couldnt find some examples. In wiki page they have given the names of some algorithms but they haven't given step by step procedures. Please ...
0
votes
0answers
17 views

Real world applications of b-chromatic number

A b-coloring of a graph G is a proper vertex coloring in which each color class have at least one vertex which is adjacent to at least one vertex in each of the other color classes. B-chromatic number ...
2
votes
1answer
12 views

Why to calculate chromatic number before coloring the graph?

This may be a noob's question, but I really want to know. What is the necessity to find the chromatic number of a graph before actually coloring it? ** Why not just color the graph and find the ...
2
votes
1answer
42 views

Colouring $n$ vertices with $(n-1)$ colours in a graph with chromatic number $n$

Suppose that a graph has chromatic number $n$. If I choose $n$ vertices of the graph such that they do not form a $K_n$ (complete graph of $n$ vertices) can I colour them with $(n-1)$ colours, such ...
2
votes
0answers
51 views

Is there a general formula for the chromatic polynomial of power set graphs?

Consider the set $A$ of $n$ elements and its power set $\mathcal{P}(n)$ represented as graph $H_n$ under the inclusion relation, For example when $n=3$, $H_3$ would look like this (ignore the ...
2
votes
1answer
52 views

Coloring a graph which is not quite complete.

Let us assume we have a graph, such that given any $n$ vertices, there is an edge missing. Can we $n$ color this graph? An example where you can do this is the line graph of a complete graph. The ...
0
votes
1answer
40 views

An easy variant of map color theorem

So the problem is to prove or disprove (or find a lower bound) that I can color equal sized disc with four different colors so that none of the touching disc shares the same color. In other words is ...
1
vote
0answers
36 views

OEIS A227133 (square-free grid colourings)

This is a nice one: http://oeis.org/A227133 (see also http://oeisf.org/Poster15a.pdf) I built a straightforward SAT encoding and found a(11) >= 72 because of ...
1
vote
1answer
59 views

Monochromatic Rectangle of a 2-Colored 8 by 8 Lattice Grid

On a $7 \times 7$ grid of points $(1,1), (1,2), \dots, (7,7)$, show that any coloring of the vertices with two different colors will result in at least one set of four points that form the vertices of ...
2
votes
3answers
55 views

Chromatic index of a complete graph

Looking to show that $\forall n \in \mathbb{N}$ $$\chi^{'}(K_{2n+2})=\chi^{'}(K_{2n+1})=2n+1$$ I'm trying to construct a colouring of the edges of $K_{2n+1}$ that leaves colour $i$ missing at vertex ...
0
votes
1answer
23 views

Prove that $\chi_l(K_{2,3})=2$

Prove that $\chi_l(K_{2,3})=2$ I know I asked question like this before, but something about this type still bugging me, so I tried more example in the book and I stumble again. Let $G=K_{2,3}$. I ...
0
votes
0answers
85 views

Proving upper bound for chromatic number for a graph with no triangles

Let $G$ be a graph with $n$ vertices, that does not contain triangles. Starting always with the vertex with the largest degree, colouring its neighbours and removing them from the graph, prove that ...
0
votes
0answers
8 views

Distance-2 Edge Coloring

Can we convert the problem of distance-2 edge coloring of G(V,E) to correspondig conflict graph G'(V'E') ? The set of all edges in G are represented as vertex set in G'. The edge present between two ...
0
votes
1answer
49 views

Trying to show that $\chi(G)(\chi(G) - 1) \leq 2m$, I think I'm almost there.

As I stated, I want to show for an arbitrary graph that $\chi(G)(\chi(G) - 1) \leq 2m$, where $m$ is the number of edges and $\gamma(G)$ is the minimal number of colors needed for a valid vertex ...
2
votes
1answer
26 views

Chromatic index of d-regular 1-connected graph

Let $G$ be a 1-vertex-connected $d$-regular graph with $d\geq2$. Find the chromatic index $\chi'(G)$. Brooks' theorem give $\Delta(G)\leq\chi'(G)\leq\Delta(G)+1$. I'm trying to look at $G'-v$, with ...
0
votes
0answers
20 views

Prove the edge chromatic number of a k-regular graph with an odd number of vertices is k+1. [duplicate]

Prove that if G is k-regular with an odd number of vertices, then the edge chromatic number of G is k+1. I'm not sure how to prove this. I know that if G is k-regular with an odd number of vertices ...
0
votes
1answer
20 views

Two-edge-colouring of $K_{5,5}$

I am not sure right now but why does every two-edge-colouring of $K_{5,5}$ has either a red or a blue matching of size $3$? Normally a complete bipartite graph $K_{r,s}$ has a maximum matching size of ...
1
vote
1answer
28 views

Bipartition and coloring

I am having hard time solving the following problem: Let $k$ be a positive integer. Then for every $2^k$ colorable graph $G=(V,E)$ we have $E=E_1 \cup \ldots \cup E_k$ and $\forall 1 \leq i \leq k ...
2
votes
0answers
52 views

Prove that every triangle-free graph is $\lceil 2\sqrt{n}\rceil$ colorable [duplicate]

Prove that every triangle-free graph is $\lceil 2\sqrt{n}\rceil$ colorable
2
votes
2answers
84 views

max degree and edge coloring

Let G be a graph with max degree $\Delta$ , then there exists a valid $(\Delta+1)$-coloring of G's edges such that each color appears $\lceil{\frac{|E|}{\Delta+1}}\rceil$ or ...
1
vote
1answer
20 views

Is a square matrix k-colorable?

Given is an $n$-by-$n$ matrix $M$ with exactly $k$ elements in each row and each column. There can be multiple elements at any position $(i,j)$ in $M$. Examples for $M$ may look like this: $M_1 = ...
2
votes
1answer
46 views

Find the upper bound for $\chi(G)$ using theorem 8.20

Given following graph a) Find the upper bound for $\chi(G)$ using theorem 8.20 b)What is $\chi(G)$? Theorem 8.20: For every graph $G$, $\chi(G) \leq 1+\max\{\delta(H)\}$, where maximum is ...
0
votes
1answer
51 views

min degree vs clique number

Show that in a graph $G$ where every two different edges are connected (i.e there is an edge incident with both) we have that $\delta<\omega+{\omega \choose 2}$ where $\delta$ is the min degree and ...
1
vote
3answers
83 views

edges in at most one odd cycle, 3 colorable

Prove that if $G$ is a graph in which every edge is a part of at most one odd length cycle, then the graph is 3 colorable. I want to show that if a graph is 4-critical there are two odd cycles which ...
1
vote
2answers
34 views

Graph with Cycle and Two-Colorable

i think if the graph G has an odd cycle, it's not two-colorable, otherwise it can be two colorable. i read in one notes that the following is True: we couldent two-colorable any graph G that has ...
3
votes
2answers
70 views

Chromatic number k+2, cycle length 2 mod k

Let $G$ be a graph with $\chi(G)=k+2$ for $k\ge3$. Prove that $G$ contains a cycle of a length $l$ such that $l \equiv 2 \;(\bmod\; k)$. Not quite sure how to approach this at all. I know that there ...
0
votes
1answer
39 views

Determine all $k$-critical graphs with $k\ge 3$ such that $G-v$ is $(k-1)$-critical $\forall v \in V(G)$

Okay, so the proof for this needs to be in two parts. I believe the answer to be $K_k$ (the complete graph on k vertices). I can show that if $G=K_k$ then $G$ is $k$-critical and $G-v$ is $(k-1)$ ...
2
votes
1answer
37 views

Chromatic number and vertex covering number

For any graph $G=(V,E)$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$. Let $\chi(G)$ denote the chromatic number of $G$. Is there a graph $G$ with $\tau(G) < \chi(G) - 1$?
0
votes
1answer
35 views

Confusion about Hajós construction?

I've read this article on the Hajós construction. I've tried to execute it in a small graph to see it's results, I guess it would be something like this: These are the incidency matrices of $G,H$ and ...
1
vote
1answer
29 views

If edges of $G$ are two colored, then there is a vertex of $G$ with at most two col0or changes in the cyclic order of the edges around the vertex.

Hello there i am reading proofs from the book of Gunter M ziegler. The chapter is called Three applications of eulers formula. Know there is a proposition which i don't fully understand and help would ...
3
votes
1answer
36 views

Every graph can be optimally colored greedily.

I was at a conference today and someone said that if the graph $G$ has chromatic number $n$ then there is a way to order the vertices so that coloring greedily gives us a coloring with $n$ colors. By ...
1
vote
1answer
41 views

Calculating chromatic polynomial for a graph

This is the graph I'm trying to find its chromatic polynomial when $\lambda = 3$ This is my solution, first take look at this theorem: Theorem : If $G = (V,E)$ is a graph and $G_1 , G_2$ are ...
0
votes
0answers
35 views

Polynomial time algorithm for finding the chromatic sum of a tree.

As the title goes, a polynomial time algorithm for finding the chromatic sum of a tree is required. NOTE: Finding the chromatic sum of a graph is also called the sum coloring problem - The sum ...
1
vote
0answers
21 views

Twisted colouring problem

I had doubts in the following similar looking questions I came across:- $Q1.$ The Cartesian plane is coloured with 2 colours. Prove that there exists 3 points of the same colour, which are the ...
0
votes
1answer
31 views

Chromatic number of a map

Since in the map each state is connect to another state we are dealing with a complete graph ($K_{12}$). Since, it is a complete graph (every state is connected to every other state), every vertex ...
1
vote
0answers
34 views

If I colour $n$ vertices independently, randomly with $n^{(1-x)}$ colours, why is the size of the colour classes $(1+o(1))n^x$?

By $o(1)$, I mean 'little-o' of $1$. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.
15
votes
3answers
363 views

Is it possible to uniquely number faces of a hexagonal grid with consecutive numbers?

You have a grid of regular hexagons. The aim of the game is to have each hex contain the numbers 1-6 on its edges. Each edge must also be connected to another edge that has a value one higher and ...
1
vote
0answers
38 views

Comparison with the greedy algorithm

Consider the following algorithm to vertex coloring: First find a maximal independent set of vertices and color these with the color 1. Then find a maximal independent set of vertices in the remaining ...
1
vote
1answer
26 views

Is there a name for this graph density measure?

Let $G=(V,E)$ be an undirected graph. We define the following procedure (randomized greedy coloring): Fix some random ordering over the vertices (each permutation will be chosen w.p. ...
2
votes
0answers
43 views

Mixing time for metropolis chain on graph coloring

I'm reading the Markov Chains and Mixing Times by David Levin et al.. In section 5.4 page 71 a proof is given for a bound of mixing time for the Metropolis Chain on graph coloring. In the proof, such ...
3
votes
1answer
192 views

Prove or disprove this upper bound on chromatic number.

Let $G$ be a simple connected finite graph and let $v \ge 4$ be the number of vertices, $E$ the number of edges, $\chi(G)$ the chromatic number , $\omega(G)$ the clique number and $\Delta$ the ...
2
votes
1answer
48 views

Finite coloring of an interval

Two real functions, $f$ and $g$, are defined on the interval $[-1,1]$. Each point $x$ in the interval is colored in one of 3 colors: Red - if $f(x)>g(x)$ Blue - if $f(x)=g(x)$ Green - if ...
0
votes
0answers
35 views

Coloring a circle

A circular spintop is colored in blue, red and green. Whenever the spintop is rotated 120 degrees, the pattern of colors looks exactly the same, only that blue becomes red, red becomes green and green ...