For questions concerned with graph colorings.

learn more… | top users | synonyms (1)

0
votes
1answer
17 views

Edge colorability of small d/k graphs - among the largest known graphs for the undirected degree diameter problem

What is known about the edge colorability of the graphs residing in the small d/k section in this table (upper left corner) ? For example, what is the chromatic index of the d=4, k=4 graph with 41 ...
4
votes
1answer
74 views

How many words can be made with $7$ A's, $6$ B's, $5$ C's and $4$ D's with no consecutive equal letters.

I would like to know how many $22$ letter words can be made that have exactly $7$ A's, $6$ B's , $5$ C's and $4$ D's and have no consecutive letters the same. This problem is clearly equivalent to ...
1
vote
1answer
41 views

Maximizing colored vertices of a graph $G$ having less than $\chi(G)$ colors

Consider a $k$-partite graph $G$ of $N$ nodes and $q$ different colors with $q < k = \chi(G)$. I would like to determine how many vertices can I color at most with these $q$ colors. Consider the ...
0
votes
0answers
11 views

Smallest near triangulation of the plane with an external face of size $4$ for which all interior vertices have minimum degree $5$?

Consider the near-triangulation $G$ with an external face of size $4$. What is the minimum number of interior vertices for which G has minimum degree 5 as to those vertices? The degrees of the $4$ ...
2
votes
1answer
36 views

An easy (or not?) collection of proper sets .

Let $S$ be a finite set. We are given $k$ rows and in each row we have two subsets of $S$ which we call them $A_i$, $B_i$ (for the $i$th row, with $i\leq k$). $A_1$ and $B_1$ $A_2$ and $B_2$ . . ...
0
votes
1answer
35 views

$ G=(V,E_1 \cup E_2) $ is a triangle free graph, where $ G_1=(V,E_1) $ is planar and $ G_2 = (V, E_2)$ is a tree. Prove that: $ \chi (G) < 7 $

can anyone help with this, any direction could be helpfull? I've tried using the fact that $ G_1 $ satisfies that it's planar and is triangle free because G is. So we should have $|E_1| \leq 2|V|-4 $ ...
5
votes
0answers
42 views

Partition Of Graph's edges Into 3 Groups

Let $G = (V, E)$ be a bipartite graph. Prove that there is a partition of the set of edges $E$ into 3 disjoint parts: $E = E1 ∪ E2 ∪ E3$, $E1 ∩ E2 = E2 ∩ E3 = E3 ∩ E1 = ∅$, so that for ...
1
vote
1answer
234 views

Connected, planar, 3-colorable graph with every face of degree 3 has an Eulerian circuit

I am trying to prove that: If G is a connected graph where every face has a degree of 3 and is 3 colourable then there exists and Euler tour. This is what I have done: For a graph to have an ...
29
votes
1answer
2k views

Is Wolfram wrong about unique 3-colorability, or am I just confused?

The illustration on Wolfram's page claims to present a uniquely colorable, triangle-free graph. However, this seems to be blatantly false: the graph has a symmetry with respect to a reflection through ...
2
votes
1answer
53 views

Doubt about claim about complexity of edge coloring powers of the line graph

Likely I am misunderstanding/missing something, but a claim in a paper appears wrong to me. According to Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation p. 2 Unless ...
2
votes
0answers
20 views

There are $m$ distinct sets of $k$ positive integers such that no two form a fat pair, show that $m<n^{k-1}$.

[ELMO 2015] Let $m, n, k > 1$ be positive integers. For a set $S$ of positive integers, define $S(i,j)$ for $i<j$ to be the number of elements in $S$ strictly between $i$ and $j$. We say two ...
0
votes
1answer
30 views

Chromatic number of a hypercube

What is the chromatic number $\chi(Q_4)$ of a four-dimensional cube. I know that all Hypercubes $Q_d$ are bipartite, so then this would yield $\chi(Q_4) = 2$, because every bipartite graph has ...
1
vote
1answer
22 views

Deriving chromatic polynomials [duplicate]

How to derive the chromatic polynomial from a Cycle? I derived the chromatic polynomial for a triangle $ K_3$ it's: $t(t-1)(t-2)$ But I don't understand how to get it for Cycles $C_n$.
2
votes
3answers
28 views

Show that one cannot make a 8×8 square using 15 T-tetrominoes and 1 square tetromino

Show that one cannot make a 8×8 square using 15 T-tetrominoes and 1 square tetromino. Its a coloring problem. Unable to solve. please help.
0
votes
2answers
31 views

Recursive equation in graph theory

How many vertex-colorings with 3 colors has the cycle $C_n$? How to build a recursive equation for the number of colorings over n? I know that a cycle has either 2 or 3 colors. 2 when n is even and ...
0
votes
1answer
79 views

Prove that a $k$-degenerate graph is ($k+1$)-colorable

A graph is $k$-degenerate if every induced subgraph contains a vertex of degree at most $k$. How can I prove that a $k$-degenerate graph is ($k+1$)-colorable?
1
vote
1answer
43 views

about petersen graph

Find the minimum number of color in Petersen graph with this condition that every vertex with all neighbor have different color ?, I think that because this graph is 3-regular then answer is at least ...
3
votes
0answers
24 views

Reference for Lovász Theta being a lower bound on the fractional chromatic number

I have recently had a chance to think about the various known lower bounds on the graph chromatic number, and how they relate to each other. Having found no single place where these relations appear, ...
0
votes
0answers
21 views

exist of k-critical graph

In the graph theory we have this theorem: my question is why exist subgraph $H^\prime$ ?,in every graph $G$ with $\chi(G)=k$ has k-critical subgraph $H$ ?
4
votes
1answer
51 views

chromatic number for $k$-regular graph

Let $G$ be a connected graph that is $k$-regular and is neither a complete graph nor an odd cycle. Then the chromatic number of $G$ is $k$. Is it true?
2
votes
2answers
40 views

Unique four-colorings of planar graphs and the like…

I am doing research into a particular graph coloring problem and wonder if someone can direct me to published work that bears on what I’m studying. It is known that planar graphs that are uniquely ...
0
votes
2answers
27 views

what is the counter example to minimality of coloring a graph in BFS manner?

i was thinking of below algorithm i use a queue Q to performs BFS and i use an arbitrary start vertex s. each vertex v has attribute v.color which specifies it's color. ...
2
votes
1answer
42 views

How to show that the Restricted-3-color decision problem is in the polynomial class

I'm struggling to answer a past paper question, which asks to prove that the defined problem is in the polynomial complexity class(P). The question is mentioned below The only strategy I can come ...
0
votes
0answers
19 views

Expected size of largest connected component in a binary matrix

Let $C_4(\mathbf M)$ and $C_8(\mathbf M)$ denote the size of binary matrix $\mathbf M$'s largest 4-connected component and 8-connected component of the same value, respectively. For example, the ...
0
votes
0answers
16 views

Existence of two-color paths between boundary vertices in a near-triangulated plane graph with an external face of degree 4

Let G be a plane graph with the following characteristics: It is near-triangulated. It has an external face of degree 4 (i.e. the graph has 4 boundary vertices, a diamond-shaped boundary ring). It ...
1
vote
1answer
49 views

Coloring the 6 vertices of a regular hexagon with a limited use per color

I want to solve to following two-part problem. I solved the first part but I am not sure how to start on part B. A) How many ways are there to color the 6 vertices of a regular hexagon using 4 colors ...
4
votes
2answers
62 views

Labelings of infinite directed acyclic graphs

Let $G=(V,E)$ be a countably infinite directed acyclic graph and $L$ be a finite set of vertex labels. The number $\left|V\right|$ of vertices is countable infinity and some vertices may have an ...
2
votes
1answer
30 views

Coloring a graph with three colors

Is the statement below correct? A graph which doesn't have a complete graph of order $4$ or more can be colored with $3$ colors, so that no two adjacent vertices have same color. I don't know it is ...
3
votes
1answer
42 views

Chromatic number $\chi(G)=600$, $P(\chi(G|_S)\leq 200) \leq 2^{-10}$

I am learning martingale and Hoeffding-Azuma inequality recently but do not how to apply the those inequality or theorem here. Let $G=(V,E)$ be a graph with chromatic number 600,i.e. $\chi(G)=600$. ...
2
votes
2answers
47 views

Upper bound for chromatic number

I'd love a hint in this problem, because don't know where to start. For any graph G it follows: $$\chi (G) \le 1 + \max\{ \delta (H):H \text{ is induced subgraph of } G\} $$ where $\delta (H) = \min ...
0
votes
1answer
40 views

Chromatic polynomial of the (hyper-)cube graph $Q_3$

How can one compute the chromatic polynomial of the (hyper-)cube graph $Q_3$? Is it easy to compute? Can we use the fact $Q_3= Q_2 \times P_2$ (where $P_2$ is the "path graph" with two vertices)?
0
votes
0answers
19 views

Find minimum number of uniformely colored rectangles in a colored grid

I have an MxN grid. In each square of the grid there is color taken from a set of color C. I can describe the whole grid with MxN statements that say something like: the square (Mi,Nj) has the color ...
5
votes
2answers
43 views

“Sparse” k-Colourings of Graphs

Is there a 4-chromatic graph $G$ and a 4-colouring $c$ of $G$ such that for every vertex $v$, the closed neighborhood $N[v] = \{v\} \cup \{ u\ |\ (v,u) \in G \}$ has at most three colours?
0
votes
1answer
75 views

Proving Welsh-Powell Algorithm

I'm proving a statement of Welsh-Powel Algorithm, that is, A graph can be colored by only using $\max_i (\min(d_i + 1, i))$ colors. I can understand why it contains $d_i$ but cannot understand the ...
1
vote
1answer
37 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
46 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
14 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
30 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
64 views

Combinatorics (coloring)

I know how to solve the two individual problems (lines alone and circles alone) but not combined.
0
votes
1answer
71 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
36 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
23 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
44 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
46 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
50 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
63 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
53 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
46 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 ...
2
votes
0answers
59 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
92 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 ...