Skip to main content
MathOverflow

Return to Question

deleted 32 characters in body; edited title
Source Link
Userbejian29
Userbejian29
  • 129
  • 5

Colouring Coloring graph with boundedmaximum vertex degree $< k$ so every vertex is a starting point for a path containing each colourcolor

Given an undirected graph ($V$ vertices, $E$ edges) with bounded degree (degree of everymaximum vertex is smaller thandegree $k$)$< k$ I want to find a vertex coloring using exactly $k$ colors so that no two adjacent vertices have the same color and for each vertex there exists a path starting in it such that no two vertices on this path has the same color and it contains exactly $k$ vertices. Additionaly, I know that in this graph there is at least one cycle of length exactly $k$. Have you got any ideas how to tackle this problem?

Colouring graph with bounded degree so every vertex is a starting point for a path containing each colour

Given an undirected graph ($V$ vertices, $E$ edges) with bounded degree (degree of every vertex is smaller than $k$) I want to find a vertex coloring using exactly $k$ colors so that no two adjacent vertices have the same color and for each vertex there exists a path starting in it such that no two vertices on this path has the same color and it contains exactly $k$ vertices. Additionaly, I know that in this graph there is at least one cycle of length exactly $k$. Have you got any ideas how to tackle this problem?

Coloring graph with maximum vertex degree $< k$ so every vertex is a starting point for a path containing each color

Given an undirected graph ($V$ vertices, $E$ edges) with maximum vertex degree $< k$ I want to find a vertex coloring using exactly $k$ colors so that no two adjacent vertices have the same color and for each vertex there exists a path starting in it such that no two vertices on this path has the same color and it contains exactly $k$ vertices. Additionaly, I know that in this graph there is at least one cycle of length exactly $k$. Have you got any ideas how to tackle this problem?

added 181 characters in body
Source Link
Userbejian29
Userbejian29
  • 129
  • 5

Given an undirected graph ($V$ vertices, $E$ edges) with bounded degree (degree of every vertex is smaller than $k$ for each vertex) I want to find a vertex coloring using exactly $k$ colors so that no two adjacent vertices have the same color and for each vertex there exists a path starting in it containingsuch that no two vertices on this path has the same color and it contains exactly $k$ vertices, each of different color. Additionaly, I know that in this graph there is at least one cycle of length exactly $k$. Have you got any ideas how to tackle this problem?

Given an undirected graph with bounded degree (degree smaller than $k$ for each vertex) I want to find a coloring using exactly $k$ colors so that no two adjacent vertices have the same color and for each vertex there exists a path starting in it containing exactly $k$ vertices, each of different color. I know that in this graph there is at least one cycle of length exactly $k$. Have you got any ideas how to tackle this problem?

Given an undirected graph ($V$ vertices, $E$ edges) with bounded degree (degree of every vertex is smaller than $k$) I want to find a vertex coloring using exactly $k$ colors so that no two adjacent vertices have the same color and for each vertex there exists a path starting in it such that no two vertices on this path has the same color and it contains exactly $k$ vertices. Additionaly, I know that in this graph there is at least one cycle of length exactly $k$. Have you got any ideas how to tackle this problem?

edited tags; edited title
Link
Userbejian29
Userbejian29
  • 129
  • 5

Colouring graph with bounded degree so every vertex is a starting point for a hamiltionian path containing each colour

Source Link
Userbejian29
Userbejian29
  • 129
  • 5