# Questions tagged [coloring]

For questions concerned with graph colorings. (This is not for mathematical art.)

1,657 questions
Filter by
Sorted by
Tagged with
33 views

### How many ways to color a circular pattern of regions such that no adjacent regions share the same color

Suppose that we have four regions $A,B,C,D$ arranged in a circular form e.g. $A$ precedes $B$, $B$ precedes $C$, $C$ precedes $D$, and $D$ precedes $A$. Using $4$ colors, how many ways can we color ...
25 views

### There exist a path of length $\chi(G)- 1$ in a connected graph G

For any undirected connected graph $G$, let $\chi (G)$ be its chromatic number. Then for every vertex $v$ in $G$, there exists a path of length $\chi (G) - 1$ starting from $v$. My approach : for ...
27 views

### Monochromatic vertex disjoint triangles in $K_{6n}$

I'm trying to show that every red/blue-colouring of the edges of $K_{6n}$ contains $n$ vertex-disjoint triangles with all $3n$ edges of the same colour. My idea is to show this by induction, we just ...
68 views

### is there a better upper bound for the Ramsey-Number for monochromatic paths with more than two colors?

Define $\rho(k,l)$ where $k \ge l$ to be $R(P_k,P_l)$, Which is the smallest number $R$ for which an $R$ clique whose edges are colored red or blue, is guaranteed to contain a red $P_k$ or a blue $P_l$...
29 views

### Every planar graph with no cycles of length $3,4,5$ is $3$-colorable.

I'm trying to prove that every planar graph with no cycles of length $3,4,5$ is $3$-colorable. However, I have no opportunity to receive any validation or correction on it, but it would be very ...
• 23
49 views

• 79
45 views

### Proving the chromatic number of this graph is $4$

I was required to prove that the following graph $G = (V, E)$ satisfies $\chi(G) = 4$: Since $C_5 \subseteq G$ we have $\chi(G) \geq 3$. Since $G$ is connected and $\Delta(G) = 5$, Brook's theorem ...
• 3,354
29 views

### Prove that for complete biclique Ki,j that ∆(Ki,j) = χ′(Ki,j).

I am trying to prove it by contradiction. Proof: "Assume that ∆(Ki,j) != χ′(Ki,j) for a complete biclique (Ki,j). If ∆(Ki,j) > χ′(Ki,j), it implies that the minimum number of colors needed to ...
112 views

### Sum of critical graphs is critical

Let $G_1$ and $G_2$ be $k_1$ and $k_2$ critical respectively. That is $\chi(G_1) = k_1$ and $\chi(G_2) = k_2$ and the removal of any vertex or edge reduces the chromatic number. I am trying to prove ...
• 511
46 views

### How Many Unique Ways Can I Color a Regular Hexagon Using 3 Colors Without Neighboring Vertices Sharing the Same Color? [closed]

I'm trying to solve a problem involving coloring a regular hexagon. Specifically, I need to color each vertex green, red, or blue, with the restriction that no neighboring vertices can have the same ...
• 17
1 vote
65 views

### Maximizing the number of colors so that every subgrid contains all colors

Consider an $n\times n$ grid. Define the set $S$ as subgrids shapes which includes all $(i,j)$ pairs so that $i\times j=n$. eg: we can take $i=1, j=n$ which is a row shape structure and it belongs to ...
28 views

### Number of ways of coloring an $m \times n$ grid such that every $2 \times 2$ square is distinct?

I recently thought of a somewhat interesting problem, which, while I've given some thought, I have no idea how to approach. The problem is stated as follows: Given an $m \times n$ grid ($m, n > 2$)...
53 views

### Proving that graph is class 2

I believe this $4$-regular graph is of class 2, i.e. its edge chromatic number is $4+1 = 5$. However, I am not able to prove it. Somehow I think that the prove should conclude that edge $\{1, 7\}$ ...
• 511
1 vote
100 views

### What does $[S]^k$ mean if $S$ is a set?

I am trying to understand a statement of Ramsey's theorem quoted by Karen R. Johannson in "Variations on a theorem by van der Waerden". She states, For every $k, m, r \in \mathbb{Z}^+$ there ...
87 views

### How many ways are there to $2$-Color an $N$ by $N$ Grid such that there is at least one $3$ by $3$ Square?

Given an $N$ by $N$ grid, how many ways are there to $2$-color the grid such that there is at least one $3$ by $3$ grid with all its four corners having the same color? Initially I had this expression ...
28 views

### Problem on the chromatic number and independent number [duplicate]

Recently, I'm learning about the chromatic number of graph theory. There is a proposition in Introduction to Graph Theory by Douglas B. West: For every graph $G$, $\chi(G) \ge \frac{n(G)}{\alpha(G)}$,...
1 vote
33 views

### For every $k \geq 2$, give an example of a regular $k$-chromatic graph that is not complete

From Graphs and Digraphs (7 ed)., we have the following exercise: 6.3. For every $k \geq 2$, give an example of a regular $k$-chromatic graph that is not complete. The examples are clear for $k = 2$ ...
• 929
67 views

### Prove that a critical graph $G$ satisfies $\chi(G) \leq \delta + 1$

Let $G = (V, E)$ a critical graph; i.e. a graph s.t. for any subgraph $H \subseteq G$ we have $\chi(H) < \chi(G)$. I was requested to prove that $\chi(G) \leq \delta + 1$, where $\delta$ is the ...
• 3,354
26 views

### Graph coloring using order arising from a Greedy coloring algorithm

Given a graph $G = (V, E)$ and an order $v_1, \ldots, v_{n}$ of its vertices, a Greedy coloring is an algorithm that assigns colors to the vertices as follows: Firstly, $c(v_1) = 0$; then it traverses ...
• 3,354
27 views

### Proving that $\chi(Q_n) = n$ where $n$ is the Queen's graph and $\gcd(n, 6) = 1$.

Let $Q_n$ be the Queen's graph with $n^2$ vertices. I was asked to show that $\chi(Q_n) = n$ whenever $6$ and $n$ are coprime. I have failed to provide a coloring that proves this for the general case....
• 3,354
68 views

### Irrigation problem as a graph coloring problem

I am trying to solve an interesting problem in graph coloring which I believe is related to the vertex cover problem. The graph is a $12 \times 12$ grid, representing a field. The field needs to be ...
1 vote
47 views

### Why is every vertex in $q$ sets?

I am reading the paper "Choosability and fractional chromatic numbers". It concerns the fractional chromatic numbers of a graph $G$: let $\mathcal{S}(G)$ be the collection of independent ...
• 2,075
22 views

### Lower bound on $\chi(G)$ + $\chi(G')$ [duplicate]

I am trying to prove that $2\sqrt{n}$ $\leq$ $\chi(G)$ + $\chi(G')$. My guess is to try squaring both sides. I know that $\chi(G)$ + $\chi(G')$ is $\leq$ n + 1. Here n is number of ...
• 85
20 views

### Reference question for a generalization of vertex coloring

I am wondering whether there is a standard convention for the following generalization of the vertex coloring. An $n$-diameter coloring is a vertex coloring such that vertices between which there ...
123 views

• 1
30 views

### Need reference for chromatic number

I need a reference (one that has a doi if possible) for the statement, "there is no general formula for finding the chromatic number of any graph"
• 323
1 vote
37 views

### Specific way to prove that a cubic graph with a cut edge isn't $3$-edge-colorable.

The statement "If a simple graph $G$ is cubic and has a cut edge, then $\chi'(G) =4$" has a couple of proofs on this site, namely here and here. However, I was interested in a specific way ...
• 7,253
18 views

### Formula for the chromatic symmetric function of a graph in terms of the graph's chromatic polynomial?

I know the chromatic symmetric function simplifies to the chromatic polynomial when 1's and 0's are subbed in for the x's. I was wondering if one could easily find the chromatic symmetric of a graph ...
• 95
1 vote
55 views

### "Subset" List Coloring for Graphs

I am interested in the following problem for research: we are given a graph $G$ and two integers $N, d$ with $N \ge d$. Say that $G$ is "$(N,d)$-subset-list colorable" if each vertex $v$ is ...
1 vote
60 views

• 161
1 vote
137 views

### Graph has at least two colorings

Let $k \geq 2$ and $G$ be an incomplete graph that is $k$-colorable and has less than $(k-1)|V(G)|-{k\choose 2}$ edges. I want to show that $G$ has at least two $k$-colorings. It looks really simple ...
• 43
82 views

### Combinatorics Coloring numbers

Let $n\ge2$ be a positive integer. We say that a positive integer $N \ge n$ is nice if, for every coloring of the positive integers $n, n + 1, n + 2, . . ., N$ in two colors, there always exists three ...
• 21
56 views

### Can you glue graphs sharing 2 edges together like graphs sharing 1 edge?

I'm working on a problem to find the chromatic polynomial $\chi_\Gamma(k)$ of this graph $\Gamma$: I know how to glue together graphs sharing 1 edge and I'm hoping I can do the same with graphs ...
• 2,271
39 views

### Combinations of doors and key rings

I've been lurking here for some years, and now finally came up with a combinatorial question to ask. :-) A company produces doors with three separate locks. Each lock has a unique key, but similar ...
• 31
1 vote
48 views

### Coloring an intersecting hypergraph [duplicate]

A hypergraph is intersecting if every two edges contain at least one common vertex. I read in a paper that for all intersecting hypergraphs, we need at most either two or three colors in order to ...
1 vote
61 views

### Counting Labeled Cyclic Graphs

I'm a grad student in Riemannian geometry. In the course of my research on a geometric problem, I found a way to formulate a key issue as a graph theory problem that I don't think is too challenging. ...
• 142
1 vote
Given an undirected connected graph $G = (V, E)$, which may contain parallel edges but excludes self-loops, it can be decomposed into $k$ subgraphs $G_1 = (V_1, E_1), \ldots, G_k = (V_k, E_k)$, where ...