Skip to main content

Questions tagged [coloring]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
Hyperbolic Cake's user avatar
2 votes
1 answer
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 ...
Arnab Seal's user avatar
0 votes
1 answer
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 ...
strugglingStudent's user avatar
3 votes
1 answer
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$...
PD_Sathya's user avatar
2 votes
1 answer
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 ...
ninaPh99's user avatar
0 votes
1 answer
49 views

Maximum number of edges in a graph on 20 vertices with no triangles

I need to find Maximum number of edges in a graph on 20 vertices with no triangles. We can conclude that $\omega(G) = 2$. Then I've tried to solve the task using chromatic number bounds. We know that $...
Jane Doe's user avatar
  • 129
0 votes
0 answers
30 views

Consequence related to Bollobas' theorem about chromatic number of a random graph [closed]

I've came across the following theorem: let $G(n,p)$ be a random graph and let $p = p(n) = n^{-\alpha}, \alpha \in (\frac{1}{2}, 1)$ then there is a function $u=u(n, \alpha)$ such that asymptotically ...
Jane Doe's user avatar
  • 129
0 votes
0 answers
10 views

Coloring graphs

Let M = {a, b, c, d, e}. We form a graph G = (V, E), where the set of vertices V consists of all subsets of two elements from set M (i.e., for example {a, d} ∈ V), and there is an edge between two ...
Kaklle K's user avatar
1 vote
1 answer
61 views

Asymptotic description giving a general result on interval coloring

Before I ask my question, let me give some definitions: Definition(Interval Coloring): Let $G$ be a loopless graph. Then, a (proper) edge coloring of $G$ with $t$ colors is called an interval $t$-...
ArsenBerk's user avatar
  • 13.3k
1 vote
1 answer
64 views

Prove, that the sequence $\{vdi(P_n)\}_{n=1}^\infty$ is increasing, where $P_n$ is a path of order $n$ and $vdi()$ is the vertex distinguishing index

Definitions Let $G$ be a graph. The vertex distinguishing index $vdi(G)$ is the minimum number of colors required for a proper edge coloring of $G$ such that any pair of vertices have distinct sets of ...
anon's user avatar
  • 539
1 vote
2 answers
74 views

Coloring 4 walls of a room with 4 colours such that no adjacent walls have same colours.

Question In how many ways, 4 walls of a room be coloured with 4 colours (R,G,B,Y) such that no adjacent walls have same colours. Attempt Let (ABCD) be walls in clockwise order, D is adjacent to A and ...
Debu's user avatar
  • 656
0 votes
0 answers
47 views

A proof of Konig's edge-coloring theorem

It is known that the convex hull of the characteristic functions of matchings in a bipartite graph is the polytope $$\{x\in\mathbb{R}^{E(G)}_{\ge 0}\mid \sum_{e\in E(G):v\in e}x_e\le 1 \text{ for ...
Connor's user avatar
  • 2,075
1 vote
0 answers
23 views

Bounding list chromatic number of a bipartite graph

Let $G$ be a bipartite graph on $n$ vertices, show that $\chi_l(G) \leq 1 + \log_2(n)$. So far I have: Let $k=1 + \log_2(n)$ and $L_1, \dots, L_n$ be $k-$element lists for the vertices of $G$. ...
strugglingStudent's user avatar
3 votes
1 answer
47 views

Let $G$ be a graph with the property: for any odd cycles $C_1, C_2$ of graph $G$, it holds that $V(C_1) \cap V(C_2) \neq \emptyset$.

Let $G$ be a graph with the property: for any odd cycles $C_1, C_2$ of graph $G$, it holds that $V(C_1) \cap V(C_2) \neq \emptyset$. (a) Let $C$ be an odd cycle in graph $G$. Prove that $\chi(G - V(C))...
hd1's user avatar
  • 79
2 votes
1 answer
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 ...
lafinur's user avatar
  • 3,354
0 votes
0 answers
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 ...
Banon Bhuiyan's user avatar
3 votes
2 answers
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 ...
mNugget's user avatar
  • 511
0 votes
1 answer
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 ...
Ruchin's user avatar
  • 17
1 vote
0 answers
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 ...
Happypantsdw's user avatar
0 votes
0 answers
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$)...
Jaculex9000's user avatar
3 votes
1 answer
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\}$ ...
mNugget's user avatar
  • 511
1 vote
1 answer
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 ...
mathy_mathema's user avatar
2 votes
1 answer
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 ...
mathy_mathema's user avatar
0 votes
0 answers
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)}$,...
HappyHhang's user avatar
1 vote
1 answer
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$ ...
Mailbox's user avatar
  • 929
2 votes
1 answer
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 ...
lafinur's user avatar
  • 3,354
0 votes
0 answers
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 ...
lafinur's user avatar
  • 3,354
0 votes
0 answers
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....
lafinur's user avatar
  • 3,354
0 votes
1 answer
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 ...
Binyamin Riahi's user avatar
1 vote
1 answer
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 ...
Connor's user avatar
  • 2,075
0 votes
0 answers
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 ...
jim's user avatar
  • 85
0 votes
1 answer
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 ...
Lactic Discomfort's user avatar
2 votes
1 answer
123 views

Lower bound on the number of complete bipartite graphs to partition the edge set of $G$

Let $bp(G)$ be the number of complete bipartite graphs needed to partition the edge set of G. This means, $ \forall e \in E(G) $, e is in exactly 1 complete bipartite graph. Now, how to prove bp(G) $ \...
jim's user avatar
  • 85
3 votes
2 answers
129 views

$ \chi (G) $ when $G$ is triangle free

Let $G$ be a triangle-free graph. Let $n_{0} = v(G)$. Now $G$ will have a an independent set of size $\lfloor \sqrt{n_{0}} \rfloor$. You can google wikipedia on triangle-free graph and you will get ...
jim's user avatar
  • 85
1 vote
1 answer
96 views

Graph colouring on $\mathbb{R}^2$. Color all points in $\mathbb{R}^2$ one of $3$ colors, show there exist $2$ points of the same color of distance $1$

Problem: (i) Show that no matter how we color all the points of the plane $\mathbb{R}^2$ in $3$ colors, there always exist two points at distance $1 $with the same color. (ii) Is it true that for ...
jim's user avatar
  • 85
0 votes
0 answers
10 views

Are there some researches about upper bound of number of k-coloring of a graph with n vertices and m edges?

Let $G$ be a graph with $n$ vertices and $m$ edges, and $A_k(G)$ be the number of $k$-coloring of $G$. If there is a matching $M$ of $G$ with $|M|=t$, then it is clear that $A_k(G)\leq (k^2-k)^{t}k^{n-...
lll's user avatar
  • 1
0 votes
0 answers
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"
Lowell0803's user avatar
1 vote
1 answer
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 ...
Robert Lee's user avatar
  • 7,253
0 votes
1 answer
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 ...
eagle I 's user avatar
1 vote
1 answer
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 ...
Ryan Dougherty's user avatar
1 vote
1 answer
60 views

Vizing's Theorem Proof, Kempe Chain

I'm trying to follow the proof of Vizing's Theorem given here https://math.uchicago.edu/~may/REU2015/REUPapers/Green.pdf Unfortunately, I soon ran into trouble with this line: If $c_k$ is absent at $...
J.D.'s user avatar
  • 93
0 votes
0 answers
74 views

Dual of LP representation of graph coloring

I have found a representation of the graph coloring problem as an ILP. Given a graph $G = (V, E)$. Let $C$ represent the set of colors. Let $w_c$ be a binary variable that is $1$ if the color $c$ is ...
mNugget's user avatar
  • 511
0 votes
1 answer
32 views

How to find this polynomial chromatic function for this graph?

I have this graph here picture. And i tried to calculate this myself with removing an edge and contracting an edge here. Below And i got my Polyomiak function to $\lambda*(\lambda-1)^{4}*(\lambda-2) -...
Jonte YH's user avatar
  • 161
1 vote
1 answer
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 ...
Norn0556's user avatar
2 votes
0 answers
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 ...
Bennett's user avatar
  • 21
0 votes
0 answers
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 ...
mjc's user avatar
  • 2,271
3 votes
0 answers
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 ...
Miika's user avatar
  • 31
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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. ...
Russ Phelan's user avatar
1 vote
1 answer
116 views

Graph coloring problem with specific graph properties

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 ...
maplemaple's user avatar
  • 1,221

1
2 3 4 5
34