The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
175 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
254 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
225 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
460 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
457 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
444 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
681 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
176 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
356 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
505 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
875 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
330 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
325 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
748 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
840 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
914 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
901 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
261 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
435 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
501 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
573 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
427 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
582 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
502 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
418 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
601 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
404 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
824 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
2answers
473 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 ...
-1
votes
1answer
1k views

Are all Hamiltonian planar graphs are 4 colorable? Does this imply all planar graphs are colorable?

Planar graphs with a Hamiltonian loop connecting all faces do not necessarily have a Hamiltonian on their edges, which would make a 3 edge coloring and thus a 4 face coloring easy. However they have a ...
14
votes
6answers
3k views

Lower bounds for chromatic number of a graph

I am trying to find a good lower bound for chromatic number of one family of graphs. I'm curious what are the known lower bounds for chromatic number. There are two obvious: $\chi(G) \geq \omega(G)$ ...
7
votes
2answers
407 views

Simple proof that these graphs are perfect

I recently came across a family of infinite graphs (in the context of two-dimensional convexity) that don't have induced 4-paths (paths with 4 vertices). Note that the complement of a 4-path is again ...
21
votes
12answers
3k 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 ...
47
votes
8answers
6k views

The “sensitivity” of 2-colorings of the d-dimensional integer lattice

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate). Let $C$ be a ...
2
votes
2answers
313 views

Colourings of Graphs with extra conditions

As a phd-student I've wandered into a question of colourings of graphs and wondered what was known about them. Given a finite graph G, where the maximum degree of a vertex is d, I'm interested in ...
12
votes
6answers
2k views

A decision problem in graph coloring

It'll be great to get a pointer or answer to the following question: What is the complexity of the following problem? Given an unweighted and undirected graph, can we have a proper (not necessarily ...
9
votes
1answer
610 views

Finding Two Rainbow Spanning Trees

Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour. Is the following problem ...
10
votes
2answers
531 views

Can we select a rainbow matching if each degree is 6 and each colorclass is a C_6?

Suppose that we have a 2d-regular graph whose edges are colored such that the edges of each color form a cycle of length 2d. (So if the graph has 2n vertices, then there are n colors.) Is it true that ...
1
vote
1answer
91 views

Graphical representation of duals of n-simplices

Is there any way to graphically represents the duals of n-simplices? For example, I want to know how exactly duals of tetrahedrons arrange between themselves, i.e how many faces, volumes share the ...
24
votes
3answers
3k 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 ...
15
votes
1answer
1k views

Making a non-monotone function monotone

Consider a function $f: \{0,1\}^n \rightarrow \{1..R\}$. This function can be interpreted as a coloring $Color(v)$ of vertices in a unit n-dimensional hypercube in $R$ colors. We say there is a ...
5
votes
4answers
983 views

Coloring Points in the Plane

Suppose one wants to color the points in the plane so any two points at distance one apart are different colors. How many colors are needed? I heard this problem when I was a kid. Back then the most ...
3
votes
2answers
504 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?
4
votes
7answers
2k views

Suggest effective heuristic (not precise) graph colouring algorithm

Can you suggest a good rough graph colouring algorithm? What are the best such algorithms nowadays?