Questions tagged [graph-colorings]
Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.
625
questions
2
votes
0
answers
87
views
Shrinking a hypergraph to a graph with identical chromatic number
Let $H=(V,E)$ be a hypergraph. A coloring is a map $c:V\to \kappa$ where $\kappa\neq \emptyset$ is a cardinal, and the restriction $c\restriction_e:e\to \kappa$ is non-constant for every $e\in E$ with ...
- 45.4k
3
votes
1
answer
102
views
What's the name of a special vertex coloring
Who knows the name of the following coloring of graphs, a proper vertex coloring so that for every vertex its every two neighbors receive different colors?
- 31.5k
4
votes
1
answer
264
views
Coloring almost-disjointness
Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$. Let $$E = \big\{\{A,B\}: A,B \in [\omega]^\omega \text{ and } |A\cap B| \text{ is finite}\big\}.$$
We consider the graph $G=...
- 2,904
4
votes
2
answers
1k
views
The number of monochromatic triangles
It is well known that the minimum number of monochromatic triangles in a red/blue coloring of the edges of the complete graph $K_n$ is given by Goodman's formula
$$M(n)=\binom n3-\left\lfloor\frac n2\...
- 6,608
1
vote
2
answers
170
views
Acyclic proper coloring of 2-degenerate graphs
A proper vertex coloring of a graph $G$ is acyclic if there is no bicolored cycle. A graph is 2-degenerate if its every subgraph has a vertex of degree at most 2. I think every 2-degenerate graph has ...
- 1,253
8
votes
2
answers
722
views
Maximum number of perfect matchings in a planar graph?
What is the maximum number of perfect matchings a planar $k$-partite $|V|$ number of vertices simple graph can have where $k=2,3,4$ ($k>4$ is impossible for a planar graph)?
Since number of ...
- 761
7
votes
1
answer
2k
views
Graphs in which any two odd cycles have a common vertex
Let $G$ be a graph in which any two odd cycles have a common vertex. It is easy to see that $\chi(G)\leq 5$ (choose minimal odd cycle $C$, use two colors for $G\setminus C$ and three colors for $C$). ...
- 103k
1
vote
0
answers
153
views
Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph
A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing's theorem states that every simple graph $G$ has a proper edge coloring using at ...
- 1,130
1
vote
0
answers
83
views
When are the 3-colorings of vertex subsets uncorrelated?
Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$.
For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct ...
- 2,852
4
votes
2
answers
2k
views
Regular graph colorings
[Since I didn't get any feedback at MSE, I dare to post this question here, too.]
Call a coloring $C:V(G) \rightarrow \lbrace 1,\dots,n \rbrace$ of a graph $G$ regular when every vertex with color $...
- 2,758
3
votes
1
answer
274
views
Chromatic number of maximal linear $k$-regular hypergraphs on $\omega$
For any integer $k>1$ we say a hypergraph $H=(\omega,E)$ where $E\subseteq {\cal P}(\omega)$ is $k$-regular if $|e|=k$ for all $e\in E$. Moreover, we say $H$ is linear if $|e_1\cap e_2|\leq 1$ for ...
- 2,758
3
votes
1
answer
143
views
Maximum weight matching with classes of edges in a multi-edge bipartite graph
Consider a multi-edge bipartite graph $G = (L, R, E)$, with $|L| = |R| = n$, such that any $x \in L, y \in R$ have precisely two edges in $E$, $(x, y)_r, (x,y)_b$. We can imagine that we are assigning ...
- 314
3
votes
1
answer
1k
views
Is there an example of converting a mathematical statement into a three color mapping? [closed]
https://youtu.be/5ovdoxnfFVc?t=1118
At this point, prof Wigderson says it is easy to go from a mathematical statement to a graph coloring problem. The video does not provide an example of this, and a ...
- 137k
2
votes
1
answer
225
views
A notion of thinness for subsets of $\omega$, using chromatic number
This is inspired by an older (as yet unanswered) question.
Let us call a set $S\subseteq\omega$ thin in the 1st sense if $$\lim\sup_{n\to\infty}\frac{|S\cap n|}{n+1}=0$$ where $\omega$ is the first ...
- 45.4k
5
votes
0
answers
178
views
Graph of number pairs summing to a square number
Consider the set $\mathbb{Z}_+$ of positive integers and set $E = \big\{\{a,b\}: a\neq b\in\mathbb{Z}_+ \text{ and there is } n\in\mathbb{Z}_+: a+b = n^2\big\}$.
Does the graph $G=(\mathbb{Z}_+,E)$ ...
- 45.4k
2
votes
1
answer
164
views
Chromatic number of rainbow hypergraphs
Let $H=(V,E)$ be a hypergraph, and $\kappa$ be a cardinal. We say that a map $c:V \to \kappa$ is a coloring if the restriction $c\restriction_e$ is non-constant whenever $e\in E$ and $|e|\geq 2$. The ...
- 11.9k
2
votes
1
answer
279
views
Decreasing the chromatic number by $2$ by removing $2$ well-chosen vertices
If you remove any $2$ vertices from a complete graph, the chromatic number gets decreased by two. (The famous double-critical graph conjecture is about the existence of a non-complete graph such that ...
- 11.9k
1
vote
1
answer
92
views
Minimizing the set of monochromatic edges
For sets $A, B$ we write $B^A$ for the set of all functions $f:A\to B$.
Let $H = (V,E)$ be a hypergraph such that $V,E\neq\varnothing$ and $|e| \geq 2$ for all $e\in E$. Let $\kappa>1$ be a ...
- 11.9k
1
vote
0
answers
230
views
Ways to Increase Chromatic Number of Graph
I'm wondering if there are known ways to increase the chromatic number of a graph, arising from a construction as follows. Suppose $G$ is a finite graph with no loops or multiple edges, and let $G_i =...
- 409
5
votes
0
answers
119
views
Equitable 4-colorings of planar triangulations
In an
equitable coloring
of a graph $G$, the number of vertices in each color class differ
by at most $1$.
For example, left below is not an equitable coloring, while the
right graph is equitably ...
- 149k
7
votes
0
answers
93
views
What is known about chromatic polynomial of hypergraph at $-1$
Let $H$ be a hypergraph and let $P_H$ denote its chromatic polynomial. I am interested in the best results interpreting $P_H(-1)$. I am interested both in the general case (which I think is hard) as ...
- 1,802
1
vote
0
answers
107
views
Connected partition number of a graph
Let $G=(V,E)$ be a finite, simple, undirected graph. We say that a partition ${\cal P}$ of $V$ into non-empty subsets of $V$ is connected if any two distinct blocks are connected by an edge, or more ...
- 45.4k
21
votes
1
answer
1k
views
Smallest known counterexamples to Hedetniemi’s conjecture
In 2019, Shitov has shown a counterexample (Ann. Math, 190(2) (2019) pp. 663-667) to Hedetniemi’s conjecture,
$$\chi(G \times H)=\min(\chi(G),\chi(H))$$
where $\chi(G)$ is the chromatic number of the ...
- 33.9k
5
votes
2
answers
260
views
Triangle coloring in random graph
Given $m$ persons (men and women) and $n$ balls, each person randomly selects $3$ balls. Once all of them complete the selection process, we color the balls with $2$ colors, white and black, such that ...
CommunityBot
- 1
3
votes
2
answers
301
views
Efficiently generating all regular/bidegreed graphs
There is a related question on how to generate all regular graphs; however, the procedure is random and repeats the generated graphs. Plus, there is no stop condition, unless recording the total ...
- 139
6
votes
1
answer
575
views
Combinatorial equation system with exponentially many equations in quadratic many variables
A certain question on graph theory (about the existance of graphs with a certain coloring inherited by perfect matchings) can be translated into the satisfiability problem of a certain set of ...
- 4,102
4
votes
0
answers
204
views
The list reaping number?
My question is inspired by a question of Dominic van der Zypen. Let $[\omega]^\omega$ denote the set of all infinite subsets of $\omega$.
The reaping number, denoted by $\mathfrak r$, is the minimum ...
- 11.9k
3
votes
1
answer
184
views
A sequence of cardinal characteristics constructed with hypergraph coloring
Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$.
A hypergraph $H=(V,E)$ consists of a set $V$ and a collection of subsets $E \subseteq {\cal P}(V)$. A coloring is a map $c: ...
- 11.9k
2
votes
0
answers
108
views
What is the optimal upper bound of $|T_1|+|T_2|+|T_3|$ if $T_1, T_2, T_3$ are trees covering a planar graph
By a classical theorem of Nash-Williams, the edges of every connected $n$-vertex planar graph can be covered by three trees $T_1,T_2$ and $T_3$. Does anyone know of any results from an article or a ...
- 39
1
vote
0
answers
75
views
Expected value of the difference of the Hadwiger number and the chromatic number
If $G$ is a finite, simple, undirected graph, its Hadwiger number $\eta(G)$ is the maximum integer $n$ such that $K_n$ is a minor of $G$. Given any integer $k>0$ let $E_k$ be the expected value of ...
- 45.4k
1
vote
0
answers
79
views
Finding strong edge coloring of a 1-subdivision of a graph such that every color is missed by some vertex of the oringinal graph
In graph theory, strong edge coloring is a proper edge coloring in which every two edges with adjacent endpoints must have different colors. A 1-subdivision of a graph results from inserting 1 new ...
- 1,130
2
votes
1
answer
100
views
Chromatic numbers of geometric duals to a fixed graph
A planar graph $G$ has some set of embeddings $\{E_\gamma:G \hookrightarrow R^2\}$.
Each of these embeddings has associated with it a geometric dual graph $G^*_\gamma$.
Using $\chi$ to denote ...
- 105
0
votes
1
answer
65
views
Collapsing non-adjacent vertices in vertex-critical graphs
We say that a finite, simple, undirected graph $G=(V,E)$ is vertex-critical if removing any vertex decreases the chromatic number.
Is there a vertex-critical graph $G=(V,E)$ and $v\neq w\in V$ with $\{...
- 22.9k
17
votes
3
answers
455
views
Graph that minimizes the number of b/w colorings where white vertices have an odd number of black
motivated from a physical context, we are currently interested in the following graph coloring problem:
Given a connected graph $G_n$ with $n$ vertices, how many colorings exist such that all white ...
- 323
0
votes
0
answers
90
views
Question about the chromatic polynomials of a graph
Let $G$ be a simple graph. Then the chromatic polynomial $X_G(q)$ has the following well-known expressions:
$$X_G(q) = \sum\limits_{\pi \in L_G}\mu(\hat 0,\pi)q^{|\pi|}$$ where $L_G$ is the set of all ...
- 1,219
3
votes
1
answer
129
views
Replacing maximum degree with degeneracy in Brooks' theorem
This is related to a previous question that I asked.
The degeneracy of a graph $G$, denoted $\mathrm{degen}(G)$, is given by $\max\{\delta(H): H\subseteq G\}$. It is well known that for all graphs $G$...
- 1,253
8
votes
1
answer
161
views
Replacing maximum degree with degeneracy in Reed's conjecture
Reed's conjecture says that $\chi(G)\leq \lceil\frac{\omega(G)+\Delta(G)+1}{2}\rceil$. One can think of $\lceil\frac{\omega(G)+\Delta(G)+1}{2}\rceil$ as the (rounded-up) average of the trivial lower ...
- 5,380
9
votes
2
answers
559
views
Do planar graphs have an acyclic two-coloring?
A graph has an acyclic two-coloring if its vertices can be colored with two colors such that each color class spans a forest.
Does every planar graph have an acyclic two-coloring?
An affirmative ...
- 31.5k
1
vote
0
answers
168
views
A query on Galvin's theorem for bipartite graphs
The Galvin's theorem is the generalized version of Dinitz conjecture that states that if the maximum degree of any bipartite graph is $\Delta$, then its edges are colorable properly if each of its ...
- 2,027
4
votes
2
answers
209
views
Graphs on $\{0,1\}^n$ based on fixed Hamming distance
Let $n$ be a positive integer and consider $\{0,1\}^n$. We define the Hamming distance $d_H(x,y)$ of members $x,y\in\{0,1\}^n$ by $$d_H(x,y)=|\big\{i\in\{0,\ldots,n-1\}:x(i)\neq y(i)\big\}|.$$
For ...
- 3,024
0
votes
1
answer
117
views
Relaxing Meyniel graphs: condition for strongly perfect instead of very strongly perfect
A Meyniel graph, $\mathcal{G}$ is a graph in which every cycle of odd length at least 5 has at least 2 chords.
First off, I have a technical question which is very important to me:
what is meant by ...
CommunityBot
- 1
2
votes
0
answers
109
views
List total chromatic number of complete graphs
Since for an odd integer $n$, a complete graph on $n$ vertices is list-edge-$n$ choosable, and the total chromatic number is $n$, it is easy to see that the list total chromatic number is bounded ...
- 60.2k
3
votes
2
answers
226
views
A problem about the connectivity of vertices that must have the same color for any proper minimal coloring of a graph
I've also posted this problem in Math Stack Exchange (here), and it now has an answer in there.
I'm trying to solve a problem about connectivity of entangled vertices in a graph.
Two vertices $u, v$ ...
- 389
7
votes
0
answers
396
views
What is this subclass of $k$-colorable graphs called?
The following property emerged naturally when I was playing with certain generalizations of Kneser graphs.
Let $k>0$ be a natural number. Consider a property $P_k$ of graphs defined as follows.
...
- 2,758
3
votes
1
answer
199
views
Chromatic number of a family of graphs
It is well-known that if a graph has maximum degree $d$, then it is $d+1$ colorable. Say we have $d+1$ graphs $G_1,\ldots, G_{d+1}$ on the same vertex set $V$, and say each $G_i$ has maximum degree at ...
- 22.2k
2
votes
0
answers
983
views
What is the number of connected graphs with $n$ vertices of max. degree up to $D$? Leaving $F(x) = x + x^2 + 2x^3 + 6x^4 + 21x^5 + 112x^6 + ...$
It is known that $F(x)$ is the generating function of the counting sequence of connected simple graphs with N vertices is given by:
$F(x) = x + x^2 + 2x^3 + 6x^4 + 21x^5 + 112x^6 + 853x^7...$
where ...
- 255
3
votes
1
answer
266
views
Evans conjecture for symmetric latin squares
The Evans conjecture ( which was proved later by Smetaniuk) states that for any $n$, if at most $n-1$ entries of a partial $n\times n$ latin square are filled, it can be completed to the full latin ...
- 178k
0
votes
0
answers
113
views
Procedure to color the edges of a circulant graph
From the first theorem in this paper, it is clear that a cayley graph on abelian group for all generating sets of even order is class $1$, that is can be edge colored in exactly $\Delta$ colors. But, ...
- 2,027
6
votes
1
answer
161
views
Embedding any graph into a vertex-transitive graph of the same chromatic number
If $G=(V,E)$ is a simple, undirected graph, is there a vertex-transitive graph $G_v$ such that $\chi(G) = \chi(G_v)$ and $G$ is isomorphic to an induced subgraph of $G_v$?
- 11.9k
1
vote
0
answers
112
views
If choosability of complement is known, can the choosability of the graph be known?
Suppose, we know that $G$ is a regular graph of odd order that is $k$- edge choosable, where $k$ is the degree. Then, is it true that $\overline{G}$ has list edge chromatic number at most $n-k+1$?
I ...
- 2,027