Search Results

A graph is $d$-degenerate if every its subgraph has a vertex of degree at most $d$. Suppose that $G$ is a graph and $G_1,G_2$ are two subgraphs of $G$ that are $d$-degenerate. Is there any way to effi …

By the Cayley's Theorem, the number of labeled tree on n vertices is at most n^{n-2}. On the other hand, what is the bound on the number of unlabeled tree on n vertices?

In graph theory, strong edge coloring is a proper edge coloring in which every two edges with adjacent endpoints must have different colors. A 1-subdivision of a graph results from inserting 1 new ver …

A graph $G$ is $d$-degenerate if every subgraph of $G$ contains a vertex of degree at most $d$. It is known that an $n$-vertex $d$-degenerate graph has at most $d(n-1)$ edges. However, if we are given …

Who knows the name of the following coloring of graphs, a proper vertex coloring so that for every vertex its every two neighbors receive different colors?

A $b$-fold coloring of a graph G is an assignment of sets of size $b$ to vertices of a graph such that adjacent vertices receive disjoint sets. An $a:b$-coloring is a $b$-fold coloring out of $a$ avai …

Yes! Let $uv$ be an edge colored by the last color, say $\Delta+1$. If $uv$ is incidence with all colors, then it is the required edge. So the only case is that every edge colored with $\Delta+1$ is n …

I do not think there is a standard name for this, but I may prefer to call it $p$-random chromatic number....

Is there a plane graph such that (1) the outer face has degree 3, i.e, is a triangle, (2) every inner face has degree 5, and (3) any two degree 5 faces share at most one commong edge.

A proper vertex coloring of a graph $G$ is acyclic if there is no bicolored cycle. A graph is 2-degenerate if its every subgraph has a vertex of degree at most 2. I think every 2-degenerate graph has …

Suppose we are given a regular dodecahedron. Then we add five crossed edges inside each of its faces (actually, inside each face it is a copy of $K_5$). It is clear that this drawing has 60 crossings. …

Let $K_{n,n}$ be a complete bipartite graph with two parts $\{u_1,u_2,\ldots,u_n\}$ and $\{v_1,v_2,\ldots,v_n\}$, and let $K^-_{n,n}$ be the graph derived from $K_{n,n}$ by delete a perfect matching $ …

A rooted tree is a tree with a distinguished root node. When a rooted tree is embedded in a plane, a cyclic ordering is induced on the subtrees of the root. Such trees are called rooted plane trees. G …

The crossing number $cr(G)$ of a graph $G$ is the lowest number of edge crossings of a plane drawing of the graph $G$. The local crossing number of a drawing of a graph is the largest number of crossi …

A graph is $k$-planar if it can be drawn in the plane so that each edge is crossed at most $k$ times. A $k$-planar graph $G$ is maximal if $G+uv$ is not $k$-planar for any non-adjacent vertices $u,v\i …