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

1
vote
0answers
11 views

A generalization of the definition of edge coloring and a related problem

A generalization of the definition of edge coloring: For any positive integer $k\geq 2$, a $k$-path edge coloring of a graph $G$ is a assignment of colors to the edges of $G$ so that for every path $...
0
votes
0answers
22 views

Permutation Invariant Color Class

$G$ is a $d$ regular graph, it has $n$ vertices. $S_n$ acts on $n$ vertices of graph $G$. Question: Does there exist a coloring algorithm for which color classes is invariant under all ...
8
votes
1answer
582 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 ...
0
votes
1answer
73 views

Choosing directed subgraph in a triangulation

Consider triangulation $T.$ Is it always possible to choose such a subgraph $H$ of $T$ that has a common edge with every face of $T$ and can be directed in such way that indegrees of all vertices of ...
0
votes
0answers
22 views

Example/ Explanation of Weisfeiler-Lehman method

I am trying to read An Optimal Lower Bound on the Number of Variables for Graph Identification. On page 3 (4th paragraph), it is written- It might color vertices and edges implicitly by using $k$-...
0
votes
0answers
26 views

Possible Number of Repetation of a Submatrix

Notation: $H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...
0
votes
0answers
136 views

Graph Coloring: Two adjacent vertices share same color

Consider, subgraphs $G_1, G_2,...... G_x$ of graph $G$. Each subgraph has $k$ vertices. Now, Fix subgraph $G_1$ and consider another subgraph $G_k$ where $1 <k \le x$. The edge set ...
2
votes
1answer
234 views

r-chromatic graphs with sufficient girth

For $k,l$ positive integers let $h(k,l)$ be the least integer with the property that in a graph on $h(k,l)$ vertices either there is a closed circuit of $k$ or fewer lines, or the graph contains $l$ ...
3
votes
0answers
64 views

Is the chromatic number of the graph of the permutahedron known?

The permutahedron $\Pi_n$ is the polytope that is the convex hull of all permutations of the vector $(1,2,...,n)$. There are many results on its structure, but I couldn't find a result on the ...
2
votes
0answers
61 views

Number of $(2n-1)$-edge-colorings of the complete graph $K_{2n}$

I just started reading about graph theory and have a question (which might be trivial). How many $(2n-1)$ edge colorings of $K_{2n}$ are there? A vaguer question: can I write $K_{4n}= K_4 + K_4 +.......
0
votes
0answers
165 views

SDP based heuristics for graph coloring

This is a question about semidefinite programming heuristics for graph vertex coloring based on the Lovasz theta number such as "Approximate Graph Coloring" by Karger, Motwani and Sudan or "A ...
4
votes
1answer
81 views

Choice number of embedded graphs

For given $g$, consider the family of graphs which may be embedded to the compact orientable surface of genus $g$. For this family, consider maximal clique $\alpha(g)$, maximal chromatic number $\chi(...
5
votes
2answers
92 views

Majority coloring for directed graphs

I came up with the following coloring concept when studying neural networks (which are often modelled using directed graphs). No idea whether there is already an established name for it. If $X$ is a ...
3
votes
2answers
105 views

Unit-Distance Polyhedra

What polyhedra are known to have two vertices adjacent if and only if they are of distance $d$ apart, for fixed $d$? For example, regular Platonic solids satisfy this condition, so I am looking for ...
7
votes
1answer
285 views

Choosing two-colorable subgraph in a triangulation

Consider a planar graph $G$ which is a triangulation. Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$? It is known that it is not always ...
-1
votes
1answer
106 views

Subgraphs of $\mathbb{R}^2$ in the Hadwiger-Nelson problem

In the setting of the Hadwiger-Nelson problem, two points of $\mathbb{R}^2$ form an edge if and only if their distance is $1$. The resulting graph $G$ has chromatic number $\chi(G)\in \{4,5,6,7\}$ and ...
13
votes
2answers
374 views

Has there been a computer search for a 5-chromatic unit distance graph?

The existence of a 4-chromatic unit distance graph (e.g., the Moser spindle) establishes a lower bound of 4 for the chromatic number of the plane (see the Nelson-Hadwiger problem). Obviously, it ...
5
votes
2answers
130 views

Finite graph colorings without symmetries

Let $G$ be a connected finite simple graph with vertex set $V$, $F$ a finite set and let $\Delta(G)$ denote the degree of $G$, i.e. $\Delta(G)= \max_{v\in V} \deg(v)$. We say that a coloring $\phi\...
1
vote
1answer
78 views

many 5-list colorings

If a graph is 4-list-colorable, then it is easy to see that it has exponentially many 5-list colorings. This is the first sentence in [Exponentially many 5-list-colorings of planar graphs,JCTB,97 (...
8
votes
1answer
121 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
65 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
114 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 edge-...
8
votes
1answer
191 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 ...
7
votes
3answers
153 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
1answer
439 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
69 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
50 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)$ ...
2
votes
1answer
82 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
1answer
216 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
1answer
82 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 NP-hard....
4
votes
1answer
76 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
0answers
74 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
59 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
0answers
33 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
1answer
97 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
106 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
3answers
768 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
1answer
165 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 ...
19
votes
0answers
271 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
1answer
62 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 $k\in\{...
1
vote
1answer
136 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 $G=(V,E)...
12
votes
5answers
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
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, ...
42
votes
12answers
5k 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 ...
31
votes
4answers
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
0answers
74 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
2answers
192 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
0answers
52 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
0answers
287 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
1answer
122 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$. ...