For questions concerned with graph colorings.

learn more… | top users | synonyms (1)

0
votes
0answers
5 views

Hypergraph $2$-colorability is NP-complete

So far all my searches for a proof of this well-known theorem have led me to the one below (Lovász 1973), reducing $k$-colorability for ordinary graphs to $2$-colorability for hypergraphs. In the ...
1
vote
0answers
23 views

Total Chromatic Number of Cycles

In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that ...
1
vote
1answer
10 views

For every simple graph like $G$ , $\chi(G) \le {(2e)}^{\frac{1}{2}}$

$\chi(G)$ The chromatic number of a graph is the smallest number of colors needed to color the vertices of so that no two adjacent vertices share the same color. Now the question : Assume that $G$ ...
0
votes
0answers
17 views

Upper bound on the list chromatic number of $d$-degenerate graphs

It can be proved that $\chi(G)\le d+1$ if $G$ is $d$-degenerate, but can we also say that $\chi_\ell(G)\le d+1$, in general[note 1]? Here, $\chi(G)$ is the chromatic number of $G$ and $\chi_\ell(G)$ ...
1
vote
1answer
32 views

A graph with list chromatic number $4$ and chromatic number $3$

What is an example of a graph with chromatic number $\chi(G)=3$ and list-chromatic number $\chi_\ell(G)=4$? My first thought was to consider complete tripartite graphs since these will have chromatic ...
0
votes
0answers
15 views

Covering $10 \times 10$ board with L tetromino

Is it possible to cover a $10 \times 10$ board using L- tetrominoes? I think the problem relates to coloring proof but can't find a suitable colouring. Any help is greatly appreciated. P.S. Can ...
1
vote
0answers
21 views

forbidden chromatic polynomial

We wish to show below chromatic polynomial are not exist; It means that we couldn't find any graph that has one of these chromatic polynomial 1- $\ k^5 - 4k^4 + 8k^3 - 4k^2 +k$ 2- $\ k^4 - 3k^3 + ...
0
votes
2answers
38 views

Show that if any two odd cycles of G have a vertex in common, then $\chi(G)$ <= 5 [closed]

A vertex coloring is an assignment of labels or colors to each vertex of a graph such that no edge connects two identically colored vertices. The most common type of vertex coloring seeks to minimize ...
0
votes
0answers
10 views

Reducing a graph without lowering its chromatic number

While trying to find an algorithm to reduce a graph without lowering its chromatic number, I made the following algorithm (but not sure if it works): Given a (simple) graph $G$, look for subgraphs ...
2
votes
2answers
19 views

Monochromatic congruent triangles on a 10-gon

Five vertices of a regular $10$-gon are painted red and five blue. Prove that there will always be two congruent monochromatic triangles. Please tell me if my proof is acceptable. I don't know how ...
0
votes
1answer
31 views

Let $G$ be a graph such that $\chi(G - x - y) = \chi(G) - 2$, for all distinct vertices $x,y$. Prove that $G$ is complete.

I understand that it's a complete graph because $\chi(K_n) = n$ (by Brooks theorem), so when we start cutting vertices, with $K_{n-1}$ we will have $\chi(K_{n-1}) = n-1$. My question is how would I ...
0
votes
0answers
17 views

Edge Chromatic Number of Product Graphs

Assume that two graphs like $G$ and $H$ are given. $G \times H$ is a graph such that every vertex of it comes from $V(G) \times V(H)$ and every vertex like $(u,v)$ is adjacent to $(u',v')$ iff : ...
1
vote
1answer
24 views

An algorithm for proper edge-coloring of every simple graph with $\delta+1$ colors

A proper $k$-edge-coloring for a graph like $G$ is coloring every $e \in E(G)$ with $k$ colors such that no two edges of the same color share a common vertex. According to Vizing Theorem, for every ...
0
votes
1answer
29 views

An example of a vertex-critical graph which is not edge-critial

$\chi(G)$ ( vertex-chromatic number of a graph like $G$) is the minimum number of colors which is enough to color every vertex of $G$ such that no two adjacent vertices have the same color. A graph ...
1
vote
1answer
33 views

Vertices coloring in Combinatorics

For graph $A$ and $B$, define $A \times B$ to have vertex set $V(A) \times V(B)$, with $(a,b)$ adjacent to $(c,d)$ if $a$ is joined to $c$ in $A$, $b$ is joined to $d$ in $B$(assume they are not the ...
2
votes
0answers
46 views

Chromatic Number and Odd Cycles

It's a well known fact that a graph is bipartite if and only if it contains no odd cycles. This is an interesting generalization: Call a sub-graph nice if it has an odd number of vertices (more than ...
1
vote
2answers
35 views

Prove that if G is a simple graph, $\chi \geq \frac{|V|^2}{|V|^2-2|E|}$

For a simple graph $G=(V,E)$, I have to prove the following bound on the chromatic number of $G$: $$\chi \geq \frac{|V|^2}{|V|^2-2|E|}$$
2
votes
1answer
36 views

How to create some large 3-regular planar graphs

I'm looking for a way to produce very large (100-2000 vertices) 3-regular planar graphs. I've tried to use plantri (plantri -m5 -v 100), but I was not able to produce only random examples (10-50 ...
-1
votes
0answers
13 views

List coloring conjecture for $K_n$ with odd $n$

The list coloring conjecture suggests that the list chromatic index is equal to the chromatic index: $\chi'(G)=\chi_L'(G)$. We were told in our lecture that this has been proven for bipartite Graphs ...
1
vote
1answer
60 views

Are $6$ hotels enough to separate $n$ mathematicians?

A convention of mathematicians will have rooms available in $6$ hotels. There are $n$ mathematicians and, because of personality conflicts, various pairs of mathematicians must be lodged in different ...
0
votes
1answer
15 views

An example of vertex transitive graph whose chromatic number and clique number is apart.

Can someone give me an example of graph have the following property? must have: the chromatic number and clique number differ more than 2, the more the better. better have: the fewer size the ...
0
votes
0answers
10 views

2COL to 2SAT clausal form

Consider the instance of lableled-2-COL given by the graph below: We can convert this problem to 2-SAT in clausal form: A hint in the question required that the first two clauses were ...
0
votes
1answer
22 views

If $G$ is a graph with $2k+1$ vertices and $|E(G)| \gt k\Delta(G)$ , then $ \chi'(G) \ge \Delta(G)+1$

We define : $\chi'(G)$ is the minimum number of colors we need in order to color all edges of the graph $G$. Assume that we have a graph like $G$ with $2k+1$ vertices and $|E(G)| \gt k\Delta(G)$. ...
1
vote
1answer
28 views

Prove that every triangle-free graph on n vertices has chromatic number at most 2√n.

How do I start the proof? Do I start by creating any triangle free graph or is there a theorem that I need to use?
0
votes
1answer
27 views

How to draw K1,3 and C5 as a cartesian product?

I've already drawn a complete bipartite graph with 1 vertex in the 'X' set and 3 vertices in the 'Y' set, but how do I fit the C5 in that graph? I can't picture it. Then how do I find the maximum ...
1
vote
1answer
41 views

Coloring problem with equilateral triangles

Prove: If we color the plain with three different colours, then there will always be an equilateral triangle which has three vertices of the same colour. I have proved it for two colours but I just ...
1
vote
1answer
41 views

Prove that every edge-coloring of $K_{17}$ with $3$ colors contains a monochromatic $K_3$. [duplicate]

Also, Prove that every edge-coloring of $K_6$ with $2$ colors contains at least two monochromatic copies of $K_3.$ I have no idea how to start these problems. What should I do?
1
vote
1answer
50 views

Find the chromatic number of the graph below.

I know the chromatic number can't be 2 because there's a cycle of 5 there. I tried 3 but to no avail. So I assume the answer is 4. But I can't prove that it's four and not three. Can someone help ...
0
votes
1answer
28 views

Let $G$ be a graph with $n$ vertices. Prove that $\chi(G) \ge \frac{n}{\alpha(G)}$

$\chi$ is the chromatic number of $G$, and $\alpha$ is the independence number of $G$. I know that if $G$ has a proper coloring, then the set of vertices with a particular color is an independent ...
1
vote
1answer
29 views

How do I prove that the vertex chromatic number of a subgraph is less than that of the original graph?

How do I prove that the vertex chromatic number of a subgraph is less than that of the original graph? Say I have a graph with chromatic number $k$. How do I prove that the chromatic number any ...
0
votes
0answers
8 views

Prove that chromatic number of a graph is less than the chromatic number of its Hajos graph.

Prove that $\chi (G) <= \chi (H (G,v_1,v_2)) <= \chi (G-v_1v_2) + 1$, where $H (G)$ is the Hajos graph of g.
0
votes
1answer
42 views

Clique number of the Hajos Construction of a Graph

Prove that $\omega(G)-1 \leq \omega(H(G,v_1,v_2)) \leq \omega(G) $. The $H(G,v1,v2)$ indicates the Hajos Construction of a graph. I can prove this for $K_n$ but I have no idea how to generalize for ...
4
votes
2answers
93 views

What is a “map” in the four color theorem?

The four color theorem declares that any map in the plane (and, more generally, spheres and so on) can be colored with four colors so that no two adjacent regions have the same colors. However, it's ...
1
vote
0answers
8 views

Cutting a colour-critical indecomposable graph

Let $G=(V,E)$ be an arbitrary indecomposable k-colour-critical graph ($k\geq4$). Is it in general possible to find a cut $C=(S,T)$, such that $S$ is a $k-1$-chromatic graph and $T$ is the complete ...
2
votes
1answer
59 views

$3$-colourings of a complete graph without monochromatic spanning trees

It is not difficult to prove that for every $2$-colouring of the edges of a complete graph, there is a monochromatic spanning tree, based on the fact that a graph or its complement has to be ...
1
vote
1answer
20 views

Chromatic number of graph obtained by removing set of edges from complete graph

Consider the complete graph on n vertices $S = (V, E)$ and let $K$ be a subset of $E$. If $k$ is the size of the maximal set of independent edges (edges with no common endpoints) in $K$, is the ...
1
vote
0answers
97 views

Circumscribed simple line arrangements are 3-colourable?

An arrangement of $s$ lines are drawn in the euclidean plane so that no three lines intersect at a common point and no two lines are parallel. Now circumscribe this arrangement by a circle so that all ...
0
votes
1answer
65 views

Counting edges in a finite connected graph where each vertex is exactly one of two values.

Let $p,q$ and $r$ be positive integers greater than $0$ with $q\neq r$. Suppose that $H$ is a finite connected graph without loops or multiedges on $p$ vertices with $q$ vertices of degree $r$, $r$ ...
0
votes
1answer
29 views

Understanding pairs of odd cycles can 5 colour a graph

Here a proof I am trying to make sense of. Let $G$ be a graph in which each pair of odd cycles shares a common vertex. Show that $\chi(G)\leq 5$. Let $C$ be any odd cycle of $G$ (if none ...
0
votes
1answer
75 views

How many ways to color a graph with 10 colors

Assume that we have ten colors to choose from. Assume that the vertices are distinguishable. How many ways are there to color the following graph? (A coloring of a graph is a painting of the vertices ...
1
vote
1answer
68 views

What is the expected number of of $k$-tuples of vertices such that all edges between the vertices have the same colour?

Consider the complete graph $K_n$ and suppose we colour each edge of $K_n$ red or blue with equal probability. For every $k$, $1\leq k \leq n$, give a formula for the expected number of $k$-tuples ...
0
votes
1answer
22 views

If a graph $G$ has a complete subgraph $K_t$, then the chromatic number $\ge t$

I'm aware of the above theorem -- namely that if a graph G contains a complete subgraph on t vertices, then the chromatic number is AT LEAST t. But, I'm wondering if anyone can show me some example ...
1
vote
2answers
31 views

If you colored every point of a circle 1 of 2 colors, is there always 2 same-colored points of distance $R$ apart?

If every point on a circle of radius $R$ in $\mathbb{R}^{2}$ were colored one of two colors, is there necessarily two points that are of the same color and of distance $R$ apart? what about $>2$ ...
1
vote
0answers
74 views

Is this proof of the four color theorem for infinite graphs legit?

So you got an infinite planar graph $G$. I will prove that it is four colorable. So, construct an infinite number of statements about graphs: The first is "is four colorable" Next, for each vertex ...
1
vote
1answer
30 views

Set Theory: Graphs and $k$-Colorings

Let $G = (V, E)$ be a graph with $V = \omega$. Show that if for all $n < \omega$, the graph $G_{n} = (n, E \cap [n]^{2})$ is $k$-colorable, then $G$ is $k$-colorable. I know how to prove this ...
1
vote
1answer
36 views

Matching numbers and colors

I'm sorry I can't ask this problem in a more formal way, the issue being that I'm not even sure what type of math this involves; I think it actually translate to a graph-coloring problem? FWIW, it's ...
1
vote
1answer
86 views

Coloring/Labelling problem in Polynomial reduction of Isomorphism

** Question :** Notice the inequality inside yellow box. If $i_1$ has $n$ possible vertex, then $j$ has maximum $(n-1)$ vertices. For $\mu_{i_1,j}$ , it should be $1\leq j \leq (n-1)$ . but it is ...
0
votes
1answer
55 views

Example of graph with specific $\chi (G)$, $\omega (G)$, $\beta (G)$

Find an original example of a graph whose chromatic number does not equal its clique number, yet whose clique partition number equals its independence number. Chromatic number: $\chi(G)$ is the ...
0
votes
1answer
30 views

Independence Number Proof Explanation

In the following proof it states that "$v_i$ is less than or equal to the independence number for all $i$." Why is this true? I know what an independence number represents, I am struggling to ...
1
vote
0answers
45 views

Greedy algorithm fails to give chromatic number

Produce a graph and degree sequence for which the greedy algorithm fails to give the chromatic number. My first example is below- The first labeling uses 2 colors which is the chromatic number and ...