Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.

learn more… | top users | synonyms

8
votes
1answer
94 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
0answers
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 ...
1
vote
0answers
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 ...
5
votes
1answer
414 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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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: ...
4
votes
1answer
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 ...
1
vote
0answers
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,\ ...
2
votes
1answer
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 ...
0
votes
1answer
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
2answers
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}$ ...
0
votes
1answer
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
1answer
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 ...
12
votes
1answer
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 ...
1
vote
0answers
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, ...
4
votes
0answers
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 ...
2
votes
0answers
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$ ...
-1
votes
1answer
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$. ...
6
votes
1answer
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
1answer
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 ...
16
votes
0answers
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 ...
11
votes
1answer
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 ...
8
votes
0answers
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
4answers
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 ...
5
votes
2answers
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$. ...
3
votes
3answers
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 ...
5
votes
1answer
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 ...
6
votes
3answers
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 ...
2
votes
0answers
67 views

Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...
0
votes
0answers
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 ...
2
votes
2answers
55 views

Minimal edge color on constraints

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every even simple cycle contains an odd number ($>1$) of colors much larger than $(\log n)^\beta$ or ...
2
votes
1answer
94 views

Images of interval edge coloring

I found out the definition of interval edge colorings, concept put by Kamalian in various papers but could not find a graph depicting an example. Where can I find pictures of explicit examples of ...
4
votes
0answers
59 views

Existence of certain graph gadget related to coloring odd hole free graph

Wondering about the existence of graph gadget related to coloring (or 3-coloring) odd hole free graphs. Let $G$ be simple $k$-chromatic connected graph with two vertices $u,v$. Is it possible $G$ to ...
0
votes
0answers
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 ...
1
vote
0answers
37 views

Stochastically coloring a graph in a local way

Suppose you are assigning values in $S$ (assume $|S|<\infty$) to nodes of a (directed) graph in a stochastic way. At the beginning, none of the node is assigned values. At the $i^{th}$ step, you ...
4
votes
1answer
112 views

Is it true that any $3$-uniform hypergraph that is not $k$-colorable must have $\Omega(k^3)$ edges?

What is the best lower bound in terms of $k$ on the number of edges in a $3$-uniform hypergraph that is not $k$-colorable? Thanks in advance.
1
vote
0answers
62 views

Proper edge colorings with no bi-colored 5-paths

Consider you want to properly edge color a graph such that it has no bi-colored cycle. Denote by $\alpha'(G)$ the least number of colors required to color the edges of $G$ in such a way. It is well ...
0
votes
0answers
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 ...
-2
votes
1answer
96 views

How does deletion-contraction affect chromatic number? Can it increase chromatic number? [closed]

Question: In graph theory, contracting an edge or deleting an edge are basic operations in many topics such as graph minors or Wagner's theorem on planar graphs. And I'm interested in how these ...
24
votes
1answer
2k views

Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946

I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph ...
18
votes
0answers
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 ...
28
votes
0answers
686 views

3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$. Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = ...
9
votes
1answer
100 views

A variant of Nelson-Hadwiger Problem on the chromatic number of the plane

The famous Nelson-Hadwiger problem asks about the chromatic number of the graph $G$, with the vertex set $V(G)={\mathbb R}^2$ where $a_1=(x_1,y_1), a_2=(x_2,y_2) \in V(G) \ $ form an edge iff ...
2
votes
1answer
143 views

How to choose a random proper coloring

I am studying proper colorings of complete bipartite graphs and I'd like to be able to pick a random proper coloring and the compute some things about it. Recall that a proper coloring of a complete ...
4
votes
0answers
151 views

Hypercube edge-coloring problem

Question: Is there a pairing (a fixed point free involution) of the vertices of the $n$-dimensional cube graph, and a $2$-coloring of its edges such that the number of color changes needed to get from ...
1
vote
1answer
129 views

a question about Brooks' Theorem for $\Delta =4$

From Brooks' 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: ...