The graph-colorings tag has no usage guidance.

**6**

votes

**0**answers

298 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

**1**answer

567 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

**1**answer

319 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

**3**answers

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

**3**

votes

**2**answers

793 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

**1**answer

248 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

**1**answer

286 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

**0**answers

195 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

**1**answer

173 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

**3**answers

283 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

**1**answer

314 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

**1**answer

228 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

**1**answer

205 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

**1**answer

598 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

**1**answer

194 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

**1**answer

189 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

**1**answer

269 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

**0**answers

243 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

**5**answers

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

**2**answers

516 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

**1**answer

470 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

**1**answer

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

**25**

votes

**2**answers

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

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

**2**

votes

**0**answers

186 views

### Maximum number of 4-colorings of planar graphs (precise version)

This is a redo of my earlier question.
I'm trying again with more precision. I ignored one of the dicta in the "how to ask" page.
For a fixed $n$, what is known (references preferred) about the ...

**3**

votes

**3**answers

368 views

### Maximum number of different 4-colorings of planar graphs of a given size

I understand that it is computationally hard to count the 4-colorings of a given graph. See answers to
this question
In a given class of planar graphs (will leave choice of class open) is there a ...

**3**

votes

**1**answer

577 views

### Graphical representation of chromatic polynomial

Suppose $c(G,u)$ is chromatic polynomial of connected simple graph $G$. We know that
$|c(G,-1)|$, as Stanley proved, is the total number of directed graph on $G$, without any cycle.
Also, we know ...

**0**

votes

**1**answer

107 views

### Counting walks on proper colorings of odd cycles

Let $G$ be an undirected odd cycle. Let $f$ be a proper 3-coloring of $G$. If $w=v_1v_2...v_k$ is a walk on $k$ vertices of $G$, let $f(w)=f(v_1)f(v_2)...f(v_k)$. Let $W_k=\{f(w)|w$ is a walk on ...

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

**6**

votes

**0**answers

345 views

### What is this subclass of $k$-colorable graphs called?

The following property emerged naturally when I was playing with certain generalizations of Kneser graphs.
Let $k>0$ be a natural number. Consider a property $P_k$ of graphs defined as follows.
...

**3**

votes

**3**answers

336 views

### Can you prove that hypergraphs with n-1 edges are partially 2 colorable?

I can. But my proof uses a theorem (which I do not reveal yet to avoid influencing you) and it feels like an overkill, so I wonder if there is a simple proof. Now the problem.
Suppose we have a ...

**0**

votes

**0**answers

200 views

### r-chromatic graphs with sufficient girth

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

**1**

vote

**1**answer

838 views

### Representations of regular maps (four color theorem)

For the scope of the four color problem and without lack of generality, maps can be represented in different ways. This is generally done to have a different perspective on the problem.
For example, ...

**3**

votes

**5**answers

1k views

### How many “different” colorings (excluding exchanges) exist for a given map (graph)?

In particular I'm interested in regular maps, excluding all maps that can be colored with 2 or 3 colors.
For what I need to analyze, maps have to be regarded as differently colored, if the same ...

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

**1**

vote

**2**answers

1k views

### code that produces all possible trees with n nodes. [closed]

I'm looking for code that produces all possible trees with no self edges (or their adjacent matrices) with n nodes, anyone have any idea if this is written anywhere?

**4**

votes

**1**answer

956 views

### Simplest examples of unique-solution and unsolvable-without-backtracking Sudoku-like problems

A
The Sudoku game admits a broad generalization as follows : let $r$ be an integer $\geq 2$
and let $X$ be a finite set, and ${\cal X}$ be a collection of $r$-subsets of $X$
(i.e, a $r$-uniform ...

**4**

votes

**1**answer

272 views

### Is the chromatic number of the real plane invariant under the norm?

Recall that chromatic number of $\mathbb{R}^2$ is the least $n$ such that there exists a function $f$ from $\mathbb{R}^2$ into a set of colors ${C_1,\ldots,C_n}$ with $f(x)\neq f(y)$ for ...

**3**

votes

**2**answers

461 views

### Edge-coloring of a graph - special case

Hi everyone,
I have a problem I am working on that can be reduced to the following special case of edge coloring.
Let $G = (V,E)$ be an arbitrary graph. Furthermore, let each edge be assigned a ...

**5**

votes

**2**answers

535 views

### 4-coloring maps of pentagons

Is there a simple proof for the 4-color theorem when restricted to (finite) maps all of whose
regions are pentagons? I am in fact most interested in convex pentagons, if that additional
structure ...

**4**

votes

**2**answers

772 views

### Coloring edges on a graph s.t. the set of edges for any two vertices have no more than 'k' colors in common

Please imagine the case where one has a planar graph, $G$, with a set of $|V|$ vertices, $(v_1, ..., v_{|V|}) \in V$, and $|E|$ edges, $(e_1, ..., e_{|E|}) \in E$. Now, provided a total of $N$ ...

**9**

votes

**2**answers

431 views

### Labelled spanning trees without edge crossings

Draw the complete graph $K_n$ on a plane in general position with every edge a straight line and randomly label the edges $0$ or $1$. Does this graph always have a spanning tree with no edges crossing ...

**4**

votes

**1**answer

698 views

### Hypergraph Chromatic Number vs Degree, Clique-Size

For a hypergraph let $\chi$ be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let $\Delta$ be ...

**2**

votes

**0**answers

134 views

### finding set of tree decompositions to cover all pairs of vertices

I first asked this on cstheory.SE but got no reply.
Let $P(X_i=x)$ represent probability that randomly chosen proper $q$-coloring of an $L\times L$ square grid contains color $x$ at position $i$. How ...

**8**

votes

**2**answers

549 views

### Derivative of Tutte polynomial at -1

Let Tutte polynomial on graph with edge-set $E$ be defined as follows
$$f(q,v)=\sum_{A\subseteq E} q^{\kappa(A)} v^{|A|}$$
Here the sum is over all subgraphs $A$, $\kappa(A)$ is the number of ...

**7**

votes

**1**answer

450 views

### Graphs with the same chromatic symmetric function

Does anyone know more examples of two nonisomorphic connected graphs with the same chromatic symmetric function? The only pair I know is the one in Stanley's paper on c.s.f.'s ...

**2**

votes

**3**answers

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

**4**

votes

**1**answer

427 views

### Bounds on strong vertex colourings of regular hypergraphs?

What are the best results for upper bounds on the number of colours required in a strong vertex colouring of a regular hypergraph H?
A regular hypergraph is one in which every vertex is contained in ...

**32**

votes

**0**answers

979 views

### Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?

A very specific case of Reed's Conjecture
Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic ...

**4**

votes

**2**answers

482 views

### Tractably Partitioning the possible vertex k-colorings of a graph by local stability and instability.

A k-coloring or k-labeling of the vertices of a single-component undirected graph G with $n$ vertices can be a proper coloring or not. If it is not a proper coloring, such that each vertex has ...