Skip to main content
2 votes
Accepted

Asymptotic description giving a general result on interval coloring

It's true that something else needs to be done here. The "straightforward" application of Fact 1 merely tells us that for all positive integers $k$, there is a graph $G$ with $\theta_{\text{...
Misha Lavrov's user avatar
2 votes
Accepted

Prove, that the sequence $\{vdi(P_n)\}_{n=1}^\infty$ is increasing, where $P_n$ is a path of order $n$ and $vdi()$ is the vertex distinguishing index

We suppose that $n\ge 3$, because the number $vdi(P_n)$ exists only for such $n$. Next, it is easy to check that $vdi(P_5)=vdi(P_6)=4$, so I guess in the question "increasing" means "...
Alex Ravsky's user avatar
  • 92.5k
2 votes
Accepted

is there a better upper bound for the Ramsey-Number for monochromatic paths with more than two colors?

Much better upper bounds are easy to prove. We have $\delta(n,t) \le nt$ by the following argument: In a $n$-edge-coloring of $K_{nt}$, there is a color class with at least $\frac1n \binom{nt}{2}$ ...
Misha Lavrov's user avatar
1 vote

There exist a path of length $\chi(G)- 1$ in a connected graph G

The statement is an easy consequence of the following preposition, which you can find in Diestel: Prep. (Diestel 5.2.2) Every $k$-chromatic graph has a subgraph of minimum degree at least $k-1$. ...
koifish's user avatar
  • 3,009
1 vote
Accepted

Every planar graph with no cycles of length $3,4,5$ is $3$-colorable.

Your proof looks pretty good to me, especially the idea for considering the size of the graph is very brilliant. Good job! The only flaw to me is the statement "every edge is on the boundary of ...
Bernard Pan's user avatar
  • 2,942
1 vote

Maximum number of edges in a graph on 20 vertices with no triangles

Suppose your graph has maximum degree $k$. Choose a vertex $x$ with $\deg x=k$. Now each of the $k$ neighbors of $x$ has degree $\le20-k$ (since $G$ has no triangles) and each of the $20-k$ non-...
user14111's user avatar
  • 1,139
1 vote
Accepted

Coloring 4 walls of a room with 4 colours such that no adjacent walls have same colours.

Here are two different human solutions, and the quick computer check. $\bf (1)$ Let us fix some painting of walls. Then a number of $n(w)$ different colors are involved, $n(w)$ is a number among $2,3,...
dan_fulea's user avatar
  • 33.9k
1 vote
Accepted

Let $G$ be a graph with the property: for any odd cycles $C_1, C_2$ of graph $G$, it holds that $V(C_1) \cap V(C_2) \neq \emptyset$.

Critique of your solution: For your writeup of (a), your initial claim of "the removal of $V(C)$ cannot disconnect $G$" is false. EG As a counterexample, take a triangle, and for each the ...
Calvin Lin's user avatar
  • 70.2k

Only top scored, non community-wiki answers of a minimum length are eligible