The graph-colorings tag has no wiki summary.
10
votes
2answers
162 views
Big Mono-Chromatic Subgraphs of Vertex 2-Colourings
I'm not a graph theorist, but the following quantity came up in my work and I'm curious if it has been studied. Given a connected finite graph $\Gamma = (V,E)$ define: $$ c(\Gamma) = \min_{f : V ...
5
votes
1answer
201 views
Bipartite Graphs arising from two k-partitions of a given Graph
Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...
12
votes
3answers
573 views
Are infinite planar graphs still 4-colorable?
Imagine you have a finite number of "sites" $S$ in the positive quadrant
of the integer lattice $\mathbb{Z}^2$,
and from each site $s \in S$, one connects $s$ to every lattice point to which it
has a ...
3
votes
1answer
52 views
How to prove a certain connection between the list-chromatic number of a bipartite graph and a cardinal?
Let $G=(L,R,E)$ be a complete bipartite graph, such that $|L|=\aleph_0$ and $|R|=\kappa$. I'd like to show that if $\kappa<2^{\aleph_0}$ then the list-chromatic number of $G$ can't be more than ...
2
votes
1answer
173 views
Coloring of subgraphs of G^n
Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , ...
3
votes
0answers
66 views
Size of b-matching constructed from b maximal matchings
The Question: Let $G$ be a (simple) graph and let $b\in\mathbb{N}$. Suppose that we have $b$ disjoint edge-subsets $M_1,\ldots , M_b$ satisfying the following condition: The set $M_1$ is a maximal ...
6
votes
1answer
204 views
What is the status of this strong form of Hedetniemi's conjecture?
In this question, a graph is a finite, undirected graph without loops or multiple edges, and a colouring of a graph is a proper vertex colouring. The product $G \times H$ of graphs $G$ and $H$ is the ...
10
votes
1answer
303 views
Coloring $K_n$ via edge-weight sums
This is a question inspired by
and tangential to "A Question on 1, 2 ,3 Conjecture"—and certainly
much easier!
Suppose one assigns a random edge weight among $\{1,2,3,\ldots,k\}$ to each
edge ...
16
votes
1answer
557 views
A Question on 1, 2 ,3 Conjecture
1, 2, 3 conjecture is well-known:
If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the numbers ...
6
votes
1answer
201 views
coloring in lattice
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 ...
2
votes
1answer
78 views
Achieving the largest possible minimum spacing between vertices of the same color in an integer lattice
Consider an infinite integer lattice, or an infinite hexagonal lattice with unit length edges. Provided a set of $k$ possible vertex colors, is there a known largest possible minimum spacing that can ...
4
votes
3answers
157 views
Crystal structure, lattice, Graph and coloring
I am working across mathematics, physics and engineering. And I am looking for whether there exists already formally established knowledge in the field.
Given a periodic graph (actually a physical ...
2
votes
1answer
157 views
When does graph Laplacian have eigenvalue -1?
Consider an undirected graph $G$ with (symmetric) adjacency matrix $A \in \{0,1\}^{n \times n}$ and degree sequence $d = (d_i)$ where $d_i = \sum_{j} A_{ij}$. Assume that every node has degree at ...
7
votes
0answers
120 views
Colouring a graph whose edge set is a special union of cliques
I am trying to show that a certain family of graphs can always be properly coloured with at most $6$ colours (where "properly coloured" means that each vertex gets a colour and no edge has both ends ...
21
votes
3answers
1k views
Can one measure the infeasibility of four color proofs?
Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...
5
votes
1answer
220 views
Minimal graphs of prescribed girth and chromatic number
The well known result of Erdős, states that
Given integers $g > 2$ and $k > 1$ there exist a graph $G$ with $\chi(G) \geq k$ and girth at least $g.$
What I am wondering is
When can we ...
5
votes
1answer
181 views
Probability that a random edge coloring of the complete graph is proper
This is a repost of this math.se question that I am posting here since it received no attention there.
What is the probability that a random edge coloring of $K_n$ with
$m \geq n$ colors ...
4
votes
1answer
93 views
Is There a Graph that is Ramsey for $P_{2n}$ but is $C_{2n+1}-$free
Write $F\to G$ to mean that for every two coloring of the edges of $F$, there exists a monochromatic copy of $G$. Nesetril and Rodl proved that for a graph $G$, there exists a graph $F\to G$ with ...
1
vote
0answers
67 views
3-edge-coloring of 3-regular multigraphs
Given that a 3-regular multigraph is 3-edge-colorable, is there an expression for how many 3-edge-colorings exist?
(For example, if a 2-regular multigraph is 2-edge-colorable, there are $2^k$ ...
0
votes
0answers
37 views
Sufficient conditions for class two criticality
Is there a condition that assures a given graph is class two critical (i.e. the removal of any edge gives a class one graph)?
5
votes
2answers
228 views
Fractional chromatic number, find reference to a particular alternate definition for
I'm searching for a reference to a particular alternate definition of the fractional chromatic number of graphs.
Let me review the most common definition and basic properties first.
Let $ G $ be ...
1
vote
3answers
206 views
Strategic vertex labeling
We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0(all vertices with ...
2
votes
1answer
250 views
bipartite graph coloring
Hi, I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is a bipartite graph G with the two vertex sets V1, V2. Each ...
0
votes
0answers
29 views
What is the complexity of finding the number (mod 2) of multicolored edges on a loop?
Let $C$ be a circuit that maps $n$-length bitstrings to elements of $\{0, 1, 2\}$. Arrange the $n$-length bitstrings in a giant loop: $0^n$ is connected to $1^n$ and $0^{n-1}1$, $0^{n-1}1$ is ...
2
votes
0answers
113 views
Clique number of a $k$th power of a graph in terms of maximum degree?
Let $G$ be a graph of maximum degree $d$. Are there any known/easy bounds on the clique number of $G^k$, in terms of $d$ and $k$? I would like something at least epsilon better than the bound on the ...
1
vote
1answer
180 views
A yes no question concerning induced group
We are given a permutation group G acting on a finite set X. Finite set $\Omega$ contains all mappings $\omega$ from the set X to finite set K. We define mapping $\hat{g}$ on the set $\Omega$ in the ...
6
votes
0answers
217 views
Maximum fractional chromatic number of a 4-regular triangle-free graph (updated)
Let $G$ be a graph with maximum degree 4 and clique number 2. The fractional version of Reed's Conjecture tells us that $\chi_f(G) \leq 7/2$. But how high can $\chi_f(G)$ be?
The Chvátal graph has ...
4
votes
1answer
353 views
Vector chromatic number and Lovasz theta
For $\alpha \ge 2$, an $\alpha$-vector coloring of a graph $X$ is an assignment of unit vectors to the vertices of $X$ such that vectors assigned to adjacent vertices have inner product less than or ...
6
votes
1answer
193 views
coincidence between minimal triangulation numbers and chromatic numbers
A friend and I were reading up on the classification of compact surfaces when we realized that the minimal number of triangles in a triangulation of the sphere, torus, and projective plane are 4 ...
8
votes
3answers
356 views
Edge-coloring of the complete graph without any rainbow paths
For a given $2k-1$ edge coloring of the complete graph $K_{2k}$,
say a Hamiltonian path $P$ is a rainbow path if every color appears exactly once in $P$.
My question is
"For each $2k (k \geq 2)$, is ...
1
vote
2answers
288 views
Coloring a graph by Maximum Independent Set extraction
recursively extracting a MIS from an undirected simple graph $G$ does produce a minimal coloring for $G$ ?
I searched extensively the internet and found a paper [1] which answer partially to this ...
2
votes
1answer
185 views
Isomorphism of connected, rigid, N-regular graphs with chromatic index N?
Background/Motivation
I'm working on algorithms for canonical labeling of a certain class of graphs (motivated by biology). The "difficult" instances of this problem can be reduced to graphs of the ...
4
votes
1answer
192 views
2-Coloring a planar hypergraph
Consider a hypergraph (of rank 3) $H = (V, E)$ (where the rank of $H$ is the maximum cardinality of a hyperedge). $H$ is said to be planar if we can construct a planar graph $G = (V, A)$, and a ...
0
votes
0answers
154 views
A copy of the Vizing's classic article about List Coloring.
Does anyone know where I get a copy of the Vizing's classic article about List Coloring?
"V. G. Vizing, Coloring the vertices of a graph in prescribed colors, Metody Diskret. Anal. v Teorii Kodov i ...
0
votes
1answer
162 views
Hypergraph coloring
I am investigating whether the following hypergraph is $2$-colorable.
Let $0\le c < d < e$ be fixed natural numbers and consider a graph on $2e$ vertices, with the vertices labelled as ...
1
vote
3answers
193 views
Chromatic number of the power set
Let $X$ be a non-empty set. Consider $\mathcal{P}(X)$, the power-set of $X$. We say that $a,b \in \mathcal{P}(X)$ form an edge if and only if their symmetric difference is a singleton, i.e. ...
1
vote
1answer
257 views
Graph Theory Terminology Question
Given a (non-multi)graph $G$ let $N_G$ be the least number of nodes that must be colored (by a single color) such that every other node in $G$ shares an edge with at least one colored node. (I am only ...
3
votes
1answer
176 views
Coloring tensor products of graphs
Let $ G,H $ are simple finite graphs and $A = G \times H$. Here $ G \times H $ is the tensor product (also called the direct or categorical product) of $ G $ and $ H $.
Let $G$ has smaller chromatic ...
4
votes
1answer
184 views
maps with a large number of 4-colorings
I brought this up in January, but now know more and can be more precise.
I will have two questions.
How much of this is known?
If you don't know the answer to 1, then who does?
I invite all ...
1
vote
1answer
356 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
votes
1answer
170 views
A Ramsey-like lower bound?
Does there exist a graph $G$ which cannot be properly vertex-coloured with 3 colours (i.e. $G$ has chromatic number at least 4), such that for every graph $H$, if $H$ contains a triangle but there ...
3
votes
1answer
170 views
What is the definition of a discharge rule?
This question is in the reverse direction of a common MO question. Instead of being faced with a formal definition and asking for some intuition for the definition, I have a concept with I understand ...
5
votes
1answer
248 views
Edge Colorings of Directed Graphs which Respect an Involution
Let G be a graph and let C be a set of coloring. Suppose that there is an involution $\phi$ from C to C. We can think about the element of C as the nonzero elements of some Abelian group and ...
7
votes
0answers
213 views
A maximum discrepancy hypergraph 2-colouring problem
This is sort of a hypergraph-ish question that I feel should be easy to prove or disprove but I can't see it right now.
The setup is as follows. We have a vertex set partitioned in to sets ...
6
votes
5answers
1k views
Highly symmetric 6-regular graph with 20 vertices
I'm interested in (node/edge-)symmetric 6-regular graphs on 20 vertices and 60 edges, especially ones with a A5/icosahedral/dodecahedral symmetry group and especially their chromatic number. So far I ...
5
votes
2answers
435 views
The Problem about 2-coloring finite plane
Suppose we color a $X \times X$ finite plane by red and blue arbitrarily. How large does X need to be to guarantee a monochromatic combinatorial square $k \times k$
1 0 1 0 1 1
1 1 1 1 1 1
1 ...
3
votes
1answer
449 views
What is the chromatic number of the graph whose vertices dimension $n-2$ subsimplicies of $\Delta^n$ and an edge between two vertices is given if the two associated $n-2$ vertices are contained in the same $n-1$ subsimplex?
Let us first remark that all of this takes place on the boundary of $\Delta^n$. The question that I wanted to solve that led to the question in the title is as follows: Let ...
2
votes
1answer
420 views
Graph Coloring - searching for some interesting problems
Hi,
I'm a high school student and writing a paper about graph coloring. Can you tell me something about some interesting problems in graph theory connected with graph coloring? Such as full triangle ...
24
votes
2answers
636 views
chromatic number of the hyperbolic plane
A notorious problem in combinatorics is the following:
If we color $\mathbb{R}^2$ so that no pair of points at unit distance get the same color, what is the fewest number of colors required?
This ...
8
votes
0answers
1k views
a new lower bound for the chromatic number of a graph?
Let S+(G) denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph G. Let S-(G) denote the sum of the squares of the negative eigenvalues and q the chromatic ...
