We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled …

Hi, I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is a bipartite graph G with the two vertex set …

Prove or Disprove: A k-regular bipartite graph (a bipartite graph where every vertex has degree k) has at least k! perfect matchings.

Let $G$ be a graph of maximum degree $d$. Are there any known/easy bounds on the clique number of $G^k$, in terms of $d$ and $k$? I would like something at least epsilon better t …

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 …

Let $C$ be a circuit that maps $n$-length bitstrings to elements of $\{0, 1, 2\}$. Arrange the $n$-length bitstrings in a giant loop: $0^n$ is connected to $1^n$ and $0^{n-1}1$, $ …

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 pr …

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? Th …

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 projecti …

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 …

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 p …

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 reduce …

I have to prove that a graph without disjoint odd cycles is 5-colourable. According to the 5-color theorem, every planar graph is 5-colourable. I think that the solution is to prov …

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 color …

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 = ( …