4
votes
1answer
34 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
32 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
20 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
41 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
36 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
18 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
30 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
41 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
56 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
24 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
43 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
28 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
36 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
35 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
78 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
30 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
62 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
48 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
81 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
38 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
56 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
100 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
40 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
240 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
42 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
71 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
46 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
57 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
43 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
44 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
157 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
103 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
163 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
113 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
59 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
50 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? ...
1
vote
1answer
122 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 ...
2
votes
2answers
174 views

Question about edge coloring and perfect matchings in regular graphs

On the wiki page for edge coloring says the following two things: "If the size of a maximum matching in a given graph is small, then many matchings will be needed in order to cover all of the edges ...
0
votes
1answer
59 views

Minimum no of colors needed to color a rectangular area with unit cells so that adjacent cells do not have the same color(with wrapping)?

Given a rectangular m x n plane with unit cells(total m.n cells), what is the minimum no. of colors required to fill the cells so that no two adjacent cells have the same color? In the normal case(no ...
2
votes
0answers
45 views

Filling a infinite colored graph with basis

This is a mathematical question raised from engineering and physics: Is there some established mathematical approach in filling a physical lattice with some colored basis (black and white here)? For ...