1
vote
1answer
28 views

How many ways can we color a $7$-cycle with $3$ colors so that no three consecutive nodes are of the same color

I have to paint graph We have three colors. The constraint is that there are no three consecutive nodes of the same color. And my idea is: All ways to paint is $3^7$ I'm going to count ...
2
votes
1answer
53 views

How many ways are there to color the $H$-shaped tree with $3$ colors such that each color is used exactly twice?

How many ways are there to color this graph with the following constraints? We have three colors: blue, red, green, and we require that the number of nodes of color green is 2, and blue 2, and red ...
0
votes
0answers
51 views

Kempe chain color swaps in a partially colored map

Crossposted to: http://mathoverflow.net/questions/179340/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using only Kempe chain color swaps (as ...
4
votes
1answer
40 views

Chromatic number of generalized hypercube

It's clear that the chromatic number of $Q_n$ is $2$. But what about the graph $G$ with vertex set ${n}^{(r)}$ where two vertices are adjacent if and only if their coordiantes differ by one? Can't ...
2
votes
0answers
35 views

Proof of chromatic number of a graph

Let $G$ be graph, let $x\in V(G)$ with $|\delta_G(x)|=\Delta(G)$. For all other nodes $v\in V(G)\setminus\{x\}$ let $|\delta_G(x)|\lt\Delta(G)$. Furthermore assume we have $v_1,v_2,v_3\in V(G)$ ...
0
votes
1answer
28 views

graph vertex chromatic number in a union of 2 sub-graphs

$G_1$ is graph on the set of vertices $\{1,2,3,4,5,6,7,8\}$, $G_1$ vertice chromatic number is 5. $G_2$ is graph on the set of vertices $\{7,8,9,10,11,12,13,14,15,17,18,19,20\}$, $G_2$ vertice ...
0
votes
2answers
44 views

Graph theory: graph coloring quesiton [duplicate]

$G_1$ is graph on the set of vertices $\{1,2,3,4,5,6,7,8\}$, $G_1$ vertice chromatic number is 5. $G_2$ is graph on the set of vertices $\{7,8,9,10,11,12,13,14,15,17,18,19,20\}$, $G_2$ vertice ...
1
vote
0answers
42 views

Edge choosability(edge list coloring) of cycles

I have 2 cycles with 6 length as shown below. I want to show that the above graph is 4-edge-choosable. I don't know where to start. It's known that every cycle of even length is 2-edge-choosable, ...
2
votes
1answer
19 views

Create a configuration - graph theory

I've encountered this (startling) difficult, to me, question: Create a configuration in the plane with a ring size 4, so that every internal vertex is of degree 5. Now, I assume I may not use ...
0
votes
1answer
34 views

3-color Graph colouring

Given a directed graph such that each node has indegree=outdegree=1 devise a algo that colour the graph such that no adjacent nodes has same color. **Note:**there is no self loop and graph has to be ...
0
votes
0answers
44 views

$k$-coloring problem which minimizes the number of conflicting vertices

Classical $k$-coloring problem (k-GCP) is to assign a color selected from $k$ colors to each vertex of graph $G$ so that the number of conflicting edges (the edges with same color endpoints) is ...
0
votes
0answers
59 views

Kempes' Flaw on 4 Color Theorem.

In The Beginner's Guide to Graph Theory by Wallis, the author introduced the flaw of Kempes' attempt to proof the four-color theorem: Kempe assumed that $G$ is a minimal planar graph requiring five ...
1
vote
0answers
28 views

If G compliment is disconnected, then chromatic number = circular chromatic number

I've been reading through a book called graph homomorphism and this is an exercise I've been trying to prove. Here's my work so far Induction on number of vertices Basis : this clearly holds ...
1
vote
0answers
45 views

Flows in signed graphs and coloring

Nowhere-zero flows and coloring of planar graphs are related by duality. (wiki) I heard that there was a similar relation for nowhere-zero flows in signed graphs and colorings of some other graphs. I ...
1
vote
1answer
41 views

coloring of a graph after removing a vertex

Let $G$ be any simple graph (i.e has no loops nor multiple edges) and let $1,2,...,\chi(G)$ be any good coloring to the vertices of $G$(i.e a minimal coloring for its vertices in which each 2 adjacent ...
0
votes
1answer
29 views

Elementary graph coloring

I have recently been introduced to graph theory, and there is that one idea I have which I am struggling with. I would like to know if this is true, and whether or not there is a somewhat simple proof ...
1
vote
1answer
39 views

Calculating Total Number of Possible 4-Colorings of a Graph

I recently met with a professor to discuss this problem and she didn't have an answer for how to do the calculation. What I did learn is that the counting itself is considered NP-Hard and is in a ...
1
vote
0answers
37 views

Which in graph theory book do you recommend for a Biologist?

I need a book in Graph Theory for my Thesis project in Biology (6 months from now). I have reasonable mathematical knowledge. The book must be strict but not as complicated as an advanced book. The ...
3
votes
1answer
45 views

Colouring bipartite graph with sets of possible colors to each vertex

I'm having some trouble with proving the following: Let $|S(v)|$ be the set of colours available to colour vertex v. The claim is that for every bipartite graph $G=(V,E)$, if $|S(v)| > log_2n$ for ...
0
votes
1answer
82 views

Five-coloring plane graphs

These days I've been reading about graph coloring. Right now I'm dealing with the five color theorem. I know how to prove that every planar graph is 6 and 5 colorable. I'm looking on the proof of the ...
0
votes
1answer
14 views

Removing a vertex from a non k-colorable graph cannot make it (k−2)-colorable

This is supposidly True in the key but a pentagon is non-4-colorable and removing a vertex (either deletion or contraction) leaves a 2 colorable graph. anyone know anything about this or is it just ...
0
votes
1answer
31 views

Show that cubic hamiltonian graph is edge-3-colourable.

How can I show that cubic hamiltonian graph is edge-3-colourable?
1
vote
0answers
66 views

Proof of Gallai's Theorem for Critical Graphs

A fundamental theorem in Graph theory is the following: Let $G$ be a $k$-critical graph with $k\geq 4$ and $G\neq K_k$. Then every block in the subgraph of $G$ induced by the vertices of degree $k-1$ ...
2
votes
0answers
50 views

References for chromatic symmetric functions of hypergraphs

Define a hypergraph to be a pair $H = (V,E)$ where $V$ is a set of vertices and $E$ is any set of subsets of $V$ called edges. Thus if every edge $U \in E$ has only two elements, then the hypergraph ...
1
vote
1answer
36 views

Graph G with two Spanning Trees

Let's assume that Graph $G = <V,E>$ has two Spanning Trees $G_a = <V, T_1>$ and $G_b = <V,T_2>$ where $T_1 \cap T_2 = \emptyset$ and $T_1 \cup T_2 = E$. Prove that $\chi(G) \le 4$ ...
3
votes
1answer
93 views

Chromatic Number and Minimum Degree

I'm wondering if it is possible to put a minimum bound on the chromatic number $X(G)$ of a graph with $n$ vertices. Namely, how would one show that $X(G) \geq n/(n-d)$, where $d$ is the minimum degree ...
0
votes
1answer
39 views

Total number of ways to color a regular graph.

I have problem stating "Find total number of ways to color a regular pentagon with 5 colors." If we consider(Exact 5 colors to color the graph) it unlabeled graph then it will be the same to ...
-1
votes
1answer
59 views

Chromatic number and vertex degree [closed]

Prove that every Graph G has at least $\chi(G)$ vertices of degree $\ge$ $\chi(G)-1$.
4
votes
1answer
123 views

Is it easy to color 3-colorable triangle-free graphs?

Grötzsch's theorem states that every planar triangle-free graph $G$ has a 3-coloring, and it is known how to efficiently find such a coloring. Moreover, if the planar condition is dropped, it is known ...
1
vote
2answers
42 views

Chromatic Polynomial for a Graph

I have The chromatic polynomial for this is given as $P(G_e,\lambda)=\lambda(\lambda-1)^3$. How is this calculated?
3
votes
1answer
261 views

Chromatic polynomial for a bipartite graph

I need to get the chromatic polynomial for the complete bipartite graph: $K_{2,3}$ Im using the Fundamental Reduction Theorem, and the picture below shows mi attempt to it. I omitted vertex names ...
2
votes
1answer
50 views

Finding a vertex of degree 3 in a penny graph to prove that it can be 4 colored

I need to prove that finite penny graphs can be 4-colored without using the 4 color theorem. It's obvious that the graph is planar and I know that I if I can always find a vertex of degree 3 then I ...
0
votes
2answers
43 views

Coloring of $K_{17}$

For any 3-coloring of $K_{17}$ I have to show there exists either a red, blue or green triangle. To start, can I use proof by contradiction with color red, blue, green? So $(0,0,136)$ means all 136 ...
0
votes
1answer
75 views

Two coloring questions and ramsays number

What is the smallest $n$ such that every 2-coloring of edges of $K_n$ contains a red or blue 4-cycle (not $K_4$)? I am given that $R(4,4) \le 18$ and $R(3,5) \le 14$ Any help is greatly appreciated!
1
vote
1answer
48 views

edge coloring of a specific graph

For the graph $D_n$ created from complete graph $K_n$ by replacing one of edges by path on 3 vertices. For example, the graph attached is $D_4$. I can prove that the edge chromatic number is $n$. ...
2
votes
1answer
58 views

Sequential algorithm for coloring graphs- there exists an ordering of vertices where it finds a coloring with $\chi(G)$ colors.

The sequential algorithm for coloring graphs is as follows Put vertices in the queue $ v_1,v_2,...,v_n$ in the order of your choice. Take out vertices from the queue and color them with the ...
2
votes
1answer
58 views

Prove, that graph $G$ has at least $\chi(G)(\chi(G)-1)/2$ edges.

Can anybody give me any hints about how to prove that for any graph $G$ the number of edges in it is at least $\chi(G)(\chi(G)-1)/2$? $\chi(G)$ is the minimal number of colors we need to use to color ...
0
votes
1answer
12 views

A consequence of edge-criticality

Let $G$ be $\Delta$-edge-critical (that is, $G$ is $\Delta + 1$-edge-chromatic and removing any edge of $G$ gives a subgraph which is at most $\Delta$-edge-chromatic, where $\Delta$ is the max degree ...
0
votes
1answer
44 views

How does this theorem of Robertson, Seymour, and Thomas imply Hadwiger's conjecture for $k$ = 6?

The result in question is Theorem Every 6-contraction-critical graph $G \neq K_6$ has a vertex $x$ such that $G-x$ is planar. The article I'm reading ("A Survey of Hadwiger's Conjecture" by Bjarne ...
0
votes
1answer
46 views

On Hadwiger's conjecture for k=4.

I'm reading the article "A Survey of Hadwiger's Conjecture" by Bjarne Toft. Toft states that the following result implies Hadwiger's conjecture for the case $k=4$: Theorem. Let $G$ be edge-maximal ...
2
votes
1answer
182 views

Edge Coloring a Complete Graph.

The problem is: Find all natural numbers $n$ for which edges of a complete graph $K_n$ can be colored red and blue so that each vertex of a complete graph has an equal number of red and blue edges? ...
3
votes
1answer
104 views

A Graph as a Union of K forests.

I want to show that a graph G that is a union of k forests has a chromatic number of at most 2k. I have narrowed my problem down to trying to show that any graph G that is a union of n trees has a ...
1
vote
1answer
167 views

3-Colorability Graph Questions

I know that a boolean formula for 3-colorability is : $ \wedge_{i \in Vertices}(\bar{b_{i,1}} \vee \bar{b_{i,2}}) \wedge_{\left(i < j \right)\in Edges} ((b_{i,1} \bigoplus b_{j,1}) \vee (b_{i,2} ...
0
votes
1answer
129 views

Chromatic number of complement of bipartite graph

What is the chromatic number of the complement of bipartite graph on $n$ vertices? If I have a complete bipartite graph $K_{1,n-1}$, then its complement are two disconnected complete graphs, $K_1$ ...
0
votes
1answer
65 views

Graph with vertex chromatic number greater than edge chromatic number

is it possible to find a graph whose vertex chromatic number = 2010 + edge chromatic number? And how to prove it? Thank for any advice.
1
vote
2answers
77 views

N-dimensional Hypercubes coloring

How many ways 3-cube vertices can be coloring using 10 color, vertices which have relation is not able to have same color. I would also appreciate anyone who show the solution for finding total ways ...
3
votes
1answer
52 views

Chromatic index of a graph with vertices of degree 3 and one of degree 2

I would like to prove that the chromatic index of a graph with vertices of degree 3 and one vertex of degree 2 is 4. I know: That this graph is in fact 3-regular graph (cubic graph) with one edge ...
0
votes
1answer
40 views

Maximum Clique Structure and Graph Coloring

How is graph coloring related to the maximum clique structure inside a graph? Also, is graph coloring problem only studied for planar graphs?
1
vote
0answers
33 views

Convert graph of triangles into edges for the sake of coloring

I have graph made of triangles, and i need to color triangles. But i already have algorithm to color edges. Is there any known algorithm to convert graph in a way to correspond edge <-> triangle? ...
2
votes
1answer
129 views

Graph Colouring - Eulerian Path

I am doing some studying for a test I have in my discrete math class and I have come across this question which I am very stuck on and keep seem to find any help... If you draw a closed curve in a ...