The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
180 views

A yes no question concerning induced group

We are given a permutation group G acting on a finite set X. Finite set $\Omega$ contains all mappings $\omega$ from the set X to finite set K. We define mapping $\hat{g}$ on the set $\Omega$ in the ...
6
votes
0answers
254 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
1answer
477 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
1answer
244 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
3answers
431 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 ...
2
votes
2answers
482 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
1answer
223 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
1answer
231 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
0answers
174 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
1answer
170 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
3answers
238 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
1answer
283 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
1answer
200 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
1answer
196 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
1answer
443 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
1answer
182 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
1answer
178 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
1answer
258 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
0answers
231 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
5answers
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
2answers
489 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
1answer
461 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
1answer
468 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 ...
24
votes
2answers
716 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 ...
8
votes
0answers
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 chromatic ...
2
votes
0answers
182 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
3answers
361 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
1answer
524 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
1answer
106 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 ...
5
votes
1answer
896 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
0answers
334 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
3answers
327 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
0answers
195 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
1answer
779 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
5answers
908 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 ...
26
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 ...
1
vote
2answers
949 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
1answer
914 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
1answer
264 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
2answers
444 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
2answers
512 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
2answers
606 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
2answers
428 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
1answer
615 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
0answers
131 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
2answers
509 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
1answer
424 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
3answers
624 views

4-colorable graphs

Hey guys, 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 iff each sub-graph G' in G ...
4
votes
1answer
414 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 ...
28
votes
0answers
856 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 ...