**8**

votes

**1**answer

95 views

### How many uniquely colored degree two vertices in 3-coloring of subcubic graph?

Is there a graph with maximum degree three that has 3 degree two vertices that must get the same (resp. different) color in every 3-coloring of the graph?
I'm interested in any similar results as ...

**1**

vote

**0**answers

49 views

### A property of minimal prime ideals in rings with finite chromatic number

Let $R$ be a commutative ring with identity. There are so many ways to associate a graph to $R$. Consider this: take the elements of $R$ (All elements including zero) as vertices an two distinct ...

**7**

votes

**1**answer

537 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 ...

**1**

vote

**0**answers

106 views

### 2-edge colorable graph approximation

A 2 edge-colorable graph is a graph in which we can color the edges with two colors, in a way such that no edges of the same color share a vertex.
Given a graph G = (V,E) I want to find a 2 ...

**8**

votes

**1**answer

185 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 ...

**6**

votes

**3**answers

142 views

### Colorings of triangulations as a generalization of the four-color problem

My question can be viewed as a generalization of the four-color problem. Instead of a planar graph, consider a triangulation of a d-sphere. One wants to color vertices with N colors so that no two ...

**5**

votes

**1**answer

416 views

### Is this graph 3-colorable?

Consider the permutations of $0,1,1,2,2,3,3.$ Each permutation is corresponding to a vertex in graph $G$. So, the graph $G$ has $630$ vertices.
Each vertex has exactly 6 neighbors. $P$ is connected ...

**2**

votes

**0**answers

49 views

### Blossoms and Colorings

There is a striking analogy between finding maximum matchings in graphs and determining the chromatic number of graphs: both problems are fairly easy for bipartite graphs, but harder, resp. too hard ...

**2**

votes

**1**answer

41 views

### Bounds on chromatic index

Let $H$ be a hypergraph of maximum vertex-degree $\Delta$. (That is, for all vertices $x$, we have $| \{ e \in H \mid x \in e \} | \leq \Delta$) Are there any bounds on the chromatic index $\chi_e(H)$ ...

**-1**

votes

**1**answer

99 views

### Reducing chromatic number

(1) Is there an estimate for maximum number of edges in a $k$ colorable $v$ vertex $d$ degree graph with genus $g$? Call this $|E|$?
(2a) What is a good estimate for worst case number of edges that ...

**2**

votes

**1**answer

77 views

### Partitioning the vertex set of a planar bipartite graph into a tree and an independent set

Let $G = (V, E)$ be a planar bipartite graph such that there is a partition $(V1, V2)$ of $V$ where $V1$ induces a tree and $V2$ induces an independent set.
Is there a characterization of such ...

**2**

votes

**1**answer

206 views

### Proof that it's possible to colour all elements in set, that all subsets will be bicolored

(For my easy understanding, let me rewrite the question. The author should feel free to remove my edit or... accept it; I am leaving the original formulation at the end intact).
=================
...

**5**

votes

**1**answer

60 views

### Algorithm for 2-coloring classes of 3-uniform hypergraphs

Hi all and thanks in advance for your efforts.
I'm interested in 2-coloring 3-uniform hypergraphs. I know that in general, the problem of deciding if a 3-uniform hypergraph is 2-colorable is ...

**4**

votes

**1**answer

71 views

### Show existence maximal clique of order $s$ in an multigraph where each vertex is colored with a set of colors

You are given a multigraph $G$ with $n$ vertices as follows:
$V := (v_1, v_2, \dots ,v_n)$
$C := \{c_1, c_2, \dots\}$, be an infinite set of colors.
$f: V \rightarrow \mathbb{P}_{\le m}(C) $, a ...

**5**

votes

**0**answers

65 views

### Chromatic numbers for coloring-constrained graphs

I am interested in any and all articles about chromatic numbers applying to constrained colorings of a graph. For example, if a graph must be (properly) colored so that there is a 2-color path ...

**2**

votes

**0**answers

57 views

### Planar triangulations for which all distinct 4-colorings consist of exactly 6 Kempe chains

Are there any internally 6-connected planar triangulations other than the icosahedron all of whose distinct 4-colorings consist of exactly 6 Kempe chains, one for each of the 6 color-pairs?
Addendum: ...

**1**

vote

**0**answers

31 views

### Colorful Neighborhoods

Given:
$G:=\{V= \{v_1,\ ...\ v_n\},E\subset V\times V\}, n<\infty$, a symmetric complete, simple graph
$w:=\ \ E \ni e_{ij}\mapsto \mathbb{R}^+$, a weight function for the edges of $G$
$K:=\{c_1,\ ...

**0**

votes

**1**answer

73 views

### Maximal chromatic number with a fixed number of edges

Given a graph $G$ with $m$ edges, what is the maximum chromatic number $\chi(G)$ that the graph can have?
My guess is that $\chi(G) \leq r(m)$ where $r(m) := \max\{k\in \mathbb{N}:
\frac{k(k-1)}{2} ...

**-1**

votes

**2**answers

98 views

### Do graphs with $\omega(G) = \chi(G)$ grow “common” as $|V|$ grows large?

On the set $[n]:= \{1,\ldots,n\}$ we consider the set $${\cal P}_2([n]) = \big\{\{a,b\}: a,b \in [n], a\neq b\big\}.$$
Since $$|{\cal P}_2([n])| =2^{n \choose 2}$$ there are exactly $2^{n\choose 2}$ ...

**2**

votes

**3**answers

759 views

### A conjectured criterion for 4-colorable graphs

I tried to find a solution to this in the web but couldn't.
Can you tell me if the following sentence is correct or else give me a counterexample?
$G$ is $4$-colorable if and only if each sub-graph ...

**12**

votes

**1**answer

157 views

### Graphs with a coloring that majorizes all other colorings

By a coloring of a graph $G = (V,E)$ I mean a map $\kappa:V\to\mathbb{N}$ such that $\kappa(u)\ne \kappa(v)$ whenever $u$ and $v$ are adjacent. (Sometimes this is called a proper coloring but I am ...

**18**

votes

**0**answers

259 views

### Coloring a Ferrers diagram

I've shopped the problem below around a bit and it seems like it might be known, or not that hard to resolve, but so far I've come up empty-handed.
Say that a coloring of the dots of a Ferrers ...

**0**

votes

**1**answer

60 views

### Weak Erdos graphs

We call a finite, simple, undirected graph $G=(V,E)$ an $n$-Erdos graph if there are $n$ subsets $S_1,\ldots, S_n$ of $V$ such that
$V = \bigcup_{n=1}^n S_n$;
each $S_k$ has $n$ elements for ...

**1**

vote

**1**answer

115 views

### Node-edge coloring of graphs

There must be work on this concept, but I am not finding it through
searches, perhaps using the wrong terminology.
Define a node-edge coloring of a graph ...

**11**

votes

**5**answers

1k views

### Can one make Erdős's Ramsey lower bound explicit?

Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number $R(k)$. Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large ...

**1**

vote

**0**answers

23 views

### Performance guarantee of RLF [closed]

I cannot manage to find the performance guarantee of the Recursive Largest First (RLF) algorithm for approximating the chromatic number of a graph.
I know DSATUR has a $\mathcal{O}(n)$ guarantee, ...

**42**

votes

**12**answers

4k 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, variations, and strengthenings of the four ...

**30**

votes

**4**answers

2k views

### Why is “P vs. NP” necessarily relevant?

I want to start out by giving two examples:
1) Graham's problem is to decide whether a given edge-coloring (with two colors) of the complete graph on vertices $\lbrace-1,+1\rbrace^n$ contains a ...

**4**

votes

**0**answers

71 views

### A relaxation of proper coloring

I am wondering if the following relaxation of proper coloring appears somewhere. I have tried some searching and have found a few relaxations of proper coloring, but none the coincides with what I ...

**8**

votes

**2**answers

182 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 ...

**2**

votes

**0**answers

51 views

### The numbers of edge colorings and partitions into vertex covers

Let $G = \langle X \cup Y, E\rangle$ be a $d$-regular bipartite graph such that $|U|=|V|=n$, and assume that $d$ divides $n$. Let $F(G)$ denote the number of proper edge colorings of $G$ using $d$ ...

**16**

votes

**0**answers

264 views

### Simpler proofs of certain Ramsey numbers

The reason for the gorgeous simplicity of the classic proofs of $R(3,3)$, $R(4,4)$, $R(3,4)$ and $R(3,5)$ is that essentially all you need is the trivial bound and a picture.
But for bigger Ramsey ...

**-1**

votes

**1**answer

107 views

### Graph such that edge contraction increases chromatic number

Let $G=(V,E)$ be a simple, undirected graph with the following properties:
Contracting any edge increases the chromatic number by $1$;
For each minor $M$ of $G$ we have $\chi(M) \leq \chi(G) + 1$.
...

**5**

votes

**2**answers

784 views

### Where can I find a catalog of known Ramsey numbers?

Is there an online catalog available of Ramsey numbers, preferably one that for unknown values documents the known upper/lower bounds?

**5**

votes

**2**answers

207 views

### How can I prove that these two graph coloring problems are polynomial time equivalent?

Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$.
...

**6**

votes

**1**answer

316 views

### Graphs in which any two odd cycle 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$). ...

**7**

votes

**1**answer

272 views

### Chromatic numbers of nowhere dense graphs

Given $c\in (0,1)$ and a graph $G=(V,E)$ such that any subset $U\subset V$ contains an independent subset of cardinality at least $c|U|$. Does it allow to bound the chromatic number $\chi(G)$ by the ...

**8**

votes

**0**answers

130 views

### Edge-colorings of plane graphs: do you know references where the following questions are studied?

Let $G$ be a plane graph (or more generally, a graph embedded on a surface) with a proper edge-coloring of $G$ with $k$ colors $\{1,\ldots,k\}$. I am interested in studying the cyclic permutations of ...

**7**

votes

**4**answers

258 views

### Graph homomorphisms and line graph

If $G,H$ are simple, undirected graphs, we say that they are in a hom(omorphism)-relation if there is a graph homomorphism from $G$ to $H$ or from $H$ to $G$.
For any graph $G$ let $L(G)$ denote its ...

**11**

votes

**1**answer

220 views

### What is the chromatic number of the “conic hypergraph” on a non-singular plane cubic?

Can we color the points of a complex non-singular plane cubic curve with finitely many colors so that no conic intersects the curve at 6 distinct points of the same color?
If so, what is the smallest ...

**0**

votes

**0**answers

46 views

### Cardinality of maximum independent set for a given degree distribution

Consider an undirected graph $G(V,E)$. Let $f_n(k)$ be the probability mass function of the degree of a vertex in $G$. Further, assume that $f_n(k)$ is a strictly decreasing function of $k$ with very ...

**0**

votes

**0**answers

27 views

### Complexity of edge coloring graphs of sufficiently large maximum degree

I am interested in the complexity of edge coloring
graphs with $\Delta(G) > |V(G)|/3$.
This is closely related to the Overfull conjecture (OC).
Conjecture/Question: If a simple graph G with n ...

**6**

votes

**1**answer

454 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 ...

**34**

votes

**5**answers

4k views

### Algebraic Proof of 4-Colour Theorem?

4-Colour Theorem. Every planar graph is 4-colourable.
This theorem of course has a well-known history. It was first proven by Appel and Haken in 1976, but their proof was met with skepticism ...

**31**

votes

**15**answers

5k views

### Strengthening the Induction Hypothesis

Suppose you are trying to prove result $X$ by induction and are getting nowhere fast. One nice trick is to try to prove a stronger result $X'$ (that you don't really care about) by induction. This ...

**3**

votes

**3**answers

103 views

### Algorithm to determine isomorphism of 2 maximal planar graphs

I read on wikipedia that there are efficient algorithms to answer the question whether 2 (maximal) planar graphs F and G are isomorphic. However, after some (IMHO) substantial searching I don't seem ...

**11**

votes

**0**answers

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 ...

**3**

votes

**1**answer

176 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 ...

**7**

votes

**1**answer

1k views

### Has anyone seen this graph?

I recently constructed the graph shown below in the process of investigating some problems regarding line graphs and homomorphisms, and then happened to see it on wikipedia. I was wondering if anyone ...

**0**

votes

**0**answers

81 views

### A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where ...