The graph-colorings tag has no wiki summary.
1
vote
0answers
12 views
a question about Brook's Theorem for $\Delta =4$
From Brook's Theorem, we know that
if a graph $G$ satisfies that $\Delta (G)=4$ and there is no $5$-clique in $G$, then $\chi (G)\leq 4$.
And it is easy to find a counterexample to the following:
...
0
votes
0answers
15 views
a special case of the Borodin-Kostochka conjecture for $\Delta (G)=4$
The Borodin-Kostochka Conjecture states that if a graph $G$ satisfies $\Delta (G)\geq 9$ and $\omega (G)\leq \Delta (G)-1$, then $\chi (G)\leq \Delta (G)-1$.
It is easy to find a counterexamples to ...
1
vote
1answer
53 views
Relationship of clique, independence, and chromatic numbers
For any graph $G=(V,E)$ let $\bar{G}$ be the complement graph. Is $$\text{inf}\big\{\frac{\omega(G)+\omega(\bar{G})}{\chi(G)} : G \text{ is a finite graph}\big\}$$ known? If not, what lower bounds are ...
1
vote
1answer
39 views
Graph of bounded continous functions with distance 1
Let $V = \{f:[0,1]\to \mathbb{R}: f \text{ is continuous}\}$ and consider the metric that is defined for $f,g\in V$ by $$d(f,g) = \max\{|f(t)-g(t)|: t\in [0,1]\}.$$
We set $E = \{\{f,g\}: f,g \in ...
4
votes
1answer
88 views
Hadwiger's conjecture for coloring number instead of chromatic number
For any graph $G=(V,E)$, the coloring number $\text{Col}(G)$ is defined to be the smallest cardinal $\kappa$ such that there is a well-ordering $\leq$ on $V$ such that for every vertex $v\in V$ we ...
1
vote
1answer
55 views
Hadwiger-Nelson problem in higher dimensions
Given a positive integer $n\in \mathbb{N}$ we define the Hadwiger-Nelson graph $\text{HN}_n$ by
$V(\text{HN}_n) = \mathbb{R}^n$;
$E(\text{HN}_n) = \{\{v_1, v_2\}: v_1, v_2 \in \mathbb{R}^n \text{ ...
6
votes
1answer
191 views
A variant to the Hadwiger-Nelson problem
Consider the following graph $G=(V,E)$ where $V=\mathbb{R}^2$ and $E = \{\{x,y\}: x,y \in \mathbb{R}^2 \text{ and } |x-y|\in \mathbb{Q}\}$.
What is $\chi(G)$?
(This is a variant of the ...
0
votes
0answers
14 views
there exists k such that all elements of A^k are positive iff G is bipartite [migrated]
How we can prove this:
Suppose G is a connected graph with adjacent matrix A. prove that there exists k such that all elements of A^k are positive iff G is bipartite. Is A^n >0 if G is not bipartite?
...
2
votes
1answer
87 views
When the vertex covering number is smaller than the chromatic number
For any graph $G=(V,E)$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$.
As noted here, we have $\tau(G) \geq \chi(G) - 1$ for all finite graphs $G$. I'm interested in graphs $G$ ...
10
votes
2answers
388 views
What is the smallest 4-chromatic graph of girth 5?
It is known that the smallest 4-chromatic graph of girth 4 is the Grötzsch graph (11 vertices). What happens for girth 5?
The Brinkmann graph (21 vertices) has chromatic number 4, girth 5 and is ...
0
votes
0answers
114 views
Prove or disprove this upper bound on chromatic number
Let $G$ be a simple connected finite graph and let $v \ge 4$ be the number of vertices, $E$ the number of edges, $\chi(G)$ the chromatic number , $\omega(G)$ the clique number and $\Delta$ the ...
4
votes
1answer
187 views
Prime labelling of graphs
A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$
such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...
2
votes
1answer
111 views
How to construct a graph with arbitrarily large girth and large chromatic number? [closed]
Erdos theorem says it is possible and it is not so easy. What is the general procedure to construct graphs like Grötzsch graph?
1
vote
0answers
39 views
Rate of convergence of graph-theoretic quantity to fractional graph-theoretic counterpart
Let $G^n$ denote the OR product of a graph with itself $n$ times, i.e. the graph which has an edge between distinct vertices $(v_1,v_2,\ldots,v_n)$ and $(u_1,u_2,\ldots,u_n)$ if there exists some $i$ ...
31
votes
9answers
3k views
Generalizations of the Four-Color theorem
The four color theorem asserts that every planar graph can be properly colored by four colors.
The purpose of this question is to collect generalizations and strengthenings of the four color theorem ...
6
votes
0answers
133 views
Does the weak Hadwiger conjecture imply the Hadwiger conjecture?
For any cardinal $\kappa$, let $K_\kappa$ denote the complete graph on $\kappa$. We consider the following statements:
(H) If $G$ is a graph and $\chi(G) = \kappa$ then $K_\kappa$ is a minor of $G$.
...
12
votes
1answer
274 views
Coloring the edges of a torus graph
Question:Consider the $2k \times 2k$ grid graph on a torus. Is it true that for every $2$-coloring of the edges, there is an antipodal pair of vertices connected by a path that changes colors at most ...
6
votes
0answers
116 views
What is known about the chromatic number for minimum-distance graphs in higher dimensions?
For a set of points in $\mathbb{R}^d$ with minimum distance $a$, the minimum-distance graph connect two points iff they are at distance $a$. We can also view it as the tangency graph for a set of ...
0
votes
2answers
103 views
Coloring of a normal map
can the following proposition be proved? If so please suggest a method. Can Kempe’s Argument be used for proof ?
Proposition: A normal map has a colouring of countries by 4 colours iff the edges of ...
8
votes
1answer
335 views
Coloring of the plane
I would like to know the minimum number k such that the plane R^2 can be coloured with k colors such that no colour contain all the possible distances. In other words, a colouring such that each color ...
1
vote
2answers
60 views
Coloring maximal independent sets with 1 color
Let $G$ be a graph and $M\subseteq V(G)$ be a maximal independent set. Is there a coloring $c:V(G)\to\chi(G)$ such that $c$ is constant on $M$?
(The answer is positive for graphs with infinite ...
1
vote
2answers
87 views
Regular graphs with strongly regular edge colorings
Given a positive integer $c>1$, for what parameters $(v,k,\lambda,\mu)$ does there exist a $c k$ regular graph on $v$ vertices that can be given an edge coloring with $c$ colors, such that the ...
2
votes
1answer
103 views
Coloring algorithm maximising color difference between neighbors
Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...
0
votes
1answer
184 views
Coin graph is 4-colorable
How can we prove that a coin graph is 4-colorable???Also, can we find any example of an non-3-colorable coin graph.
2
votes
1answer
213 views
On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections
Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements.
We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we ...
3
votes
1answer
79 views
Coloring graph such that the coloring classes are not maximal independent sets
Let $G$ be a (finite or infinite) simple graph. We let $\mathrm{Ind}(G)$ be the collection of independent sets. For any cardinal $\kappa$ and coloring map $\chi: G\to \kappa$ we have ...
1
vote
0answers
142 views
Kempe chain color swaps in a partially colored map
Crossposted from math.stackexchange.com:
http://math.stackexchange.com/questions/904932/kempe-chain-color-swaps-in-a-partially-colored-map
Question: In this partially Tait's colored map, using ...
6
votes
2answers
277 views
Matching number and chromatic number
If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$).
For odd integers $n$ we have $n=\chi(K_n) = ...
0
votes
0answers
75 views
asymptotic notation with graph colouring
This is my first ever post so I hope this is an appropriate question.
Basically I am looking at the paper here: http://homepages.math.uic.edu/~mubayi/papers/biclique.pdf
Namely theorem 5.
Now, feel ...
2
votes
0answers
190 views
Computing the chromatic polynomial of graph modulo $x-3$
The chromatic polynomial of graph $P(G,x)$ is univariate
polynomial which counts the number of colorings of $G$
with $x$ colors for natural $x$.
Graph is not $k$ colorable iff $P(G,k)=0$.
The ...
7
votes
2answers
211 views
Conjecture: for perfect graphs the fractional chromatic index rounded up equals the chromatic index
Let $\chi'_f(G)$ be the fractional chromatic index.
Based on limited experiments (up to 8 vertices and few larger graphs),
I suspect:
Conjecture For perfect graphs $\lceil \chi'_f(G) \rceil = ...
8
votes
1answer
342 views
Postnikov's approach to perfect matchings of graphs
Over a decade ago Alexander Postnikov developed his own way of looking at perfect matchings of bipartite plane graphs. As I recall, he starts with a 2-coloring of the square grid and creates a new ...
6
votes
0answers
146 views
The Universal Labeling of graph
The universal labeling of a graph $G$ is a labeling of the edge set in $G$ such that in every orientation $\ell$ of $G$ for every two adjacent vertices $v$ and $u$, the sum of incoming edges of $v$ ...
34
votes
6answers
3k views
Is it easy to produce hard-to-color graphs?
This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
7
votes
2answers
138 views
Bounds on chromatic number of $k$-planar graphs
A $1$-planar graph can be drawn in the
plane so that each arc is crossed at most once by another arc.
A $k$-planar graph can be drawn so that each arc is crossed at most $k$ times.
Planar graphs are ...
0
votes
0answers
31 views
number of bipolar orientations to acyclic ones
Given a $k$-regular graph $G$, is there an upper bound on the number of bipolar orientations that $G$ has?
I am trying to show that the number of bipolar orientations is much much lower than the ...
3
votes
1answer
60 views
Graph construction to double coloring & Hadwiger number
For any graph $G$ let $\eta(G)$ be the Hadwiger number of $G$.
Is there for every graph $G$ a graph $2G$ such that
-- $\chi(2G) = 2\chi(G)$, and
-- $\eta(2G) = 2\eta(G)$?
For each one of the above ...
3
votes
0answers
88 views
Independence Number of K4-free planar graphs
The independence ratio is defined as the size of the maximum independent set divided by $n$. By the 4-color theorem, every planar graph with $n$ vertices has independence ratio at least $1/4$. ...
10
votes
2answers
182 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
377 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 ...
13
votes
3answers
705 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
68 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
192 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
82 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
267 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
321 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
710 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 ...
5
votes
1answer
314 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
136 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 ...
3
votes
3answers
229 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 ...
