Skip to main content
added 120 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Yes, and we do not even use the restrictions on mutual intersections of edges. For weak colorings, we may replace each edge with at least 2 vertices to an edge with exactly 2 vertices (possibly we get the same edge several times). It remains to properly color a graph with $n\geqslant 2$ edges with $n$ colors. This is done by induction: color any vertex of any edge in a color $n-1$, remove the edges incident to this vertex and proceed.

Moreover, if $c$ is a positive integer such that $c(c+1)/2\geqslant n+1$, then $c$ colors suffice. Indeed, if not, we may find a subgraph with all degrees at least $c$ (obtained by consecutive removing the vertices with degree less than $c$), it has at least $c+1$ vertices, thus at least $c(c+1)/2>n$ edges, a contradiction.

Yes. For weak colorings, we may replace each edge with at least 2 vertices to an edge with exactly 2 vertices. It remains to properly color a graph with $n\geqslant 2$ edges with $n$ colors. This is done by induction: color any vertex of any edge in a color $n-1$, remove the edges incident to this vertex and proceed.

Moreover, if $c$ is a positive integer such that $c(c+1)/2\geqslant n+1$, then $c$ colors suffice. Indeed, if not, we may find a subgraph with all degrees at least $c$ (obtained by consecutive removing the vertices with degree less than $c$), it has at least $c+1$ vertices, thus at least $c(c+1)/2>n$ edges, a contradiction.

Yes, and we do not even use the restrictions on mutual intersections of edges. For weak colorings, we may replace each edge with at least 2 vertices to an edge with exactly 2 vertices (possibly we get the same edge several times). It remains to properly color a graph with $n\geqslant 2$ edges with $n$ colors. This is done by induction: color any vertex of any edge in a color $n-1$, remove the edges incident to this vertex and proceed.

Moreover, if $c$ is a positive integer such that $c(c+1)/2\geqslant n+1$, then $c$ colors suffice. Indeed, if not, we may find a subgraph with all degrees at least $c$ (obtained by consecutive removing the vertices with degree less than $c$), it has at least $c+1$ vertices, thus at least $c(c+1)/2>n$ edges, a contradiction.

added 342 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Yes. For weak colorings, we may replace each edge with at least 2 vertices to an edge with exactly 2 vertices. It remains to properly color a graph with $n$$n\geqslant 2$ edges with $n$ colors. This is done by induction: color any vertex of any edge in a color $n-1$, remove the edges incident to this vertex and proceed.

Moreover, if $c$ is a positive integer such that $c(c+1)/2\geqslant n+1$, then $c$ colors suffice. Indeed, if not, we may find a subgraph with all degrees at least $c$ (obtained by consecutive removing the vertices with degree less than $c$), it has at least $c+1$ vertices, thus at least $c(c+1)/2>n$ edges, a contradiction.

Yes. For weak colorings, we may replace each edge with at least 2 vertices to an edge with exactly 2 vertices. It remains to properly color a graph with $n$ edges with $n$ colors. This is done by induction: color any vertex of any edge in a color $n-1$, remove the edges incident to this vertex and proceed.

Yes. For weak colorings, we may replace each edge with at least 2 vertices to an edge with exactly 2 vertices. It remains to properly color a graph with $n\geqslant 2$ edges with $n$ colors. This is done by induction: color any vertex of any edge in a color $n-1$, remove the edges incident to this vertex and proceed.

Moreover, if $c$ is a positive integer such that $c(c+1)/2\geqslant n+1$, then $c$ colors suffice. Indeed, if not, we may find a subgraph with all degrees at least $c$ (obtained by consecutive removing the vertices with degree less than $c$), it has at least $c+1$ vertices, thus at least $c(c+1)/2>n$ edges, a contradiction.

Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Yes. For weak colorings, we may replace each edge with at least 2 vertices to an edge with exactly 2 vertices. It remains to properly color a graph with $n$ edges with $n$ colors. This is done by induction: color any vertex of any edge in a color $n-1$, remove the edges incident to this vertex and proceed.