An edge weighting $\omega : E \rightarrow \{1,2, \ldots, k\}$ of a graf $G=(V,E)$ induces a vertex colouring where vertex colour is defined as a sum of weights on incident edges. The smallest $k$ for which there exists an edge weighting which induces a proper colouring is denoted by $\chi_\Sigma^e(G)$. If a graph contains an isolated edge then such a weighting does not exist. Therefore, we only consider graphs without isolated edges. We focus on providing constant upper bounds for parameter $\chi_\Sigma^e(G)$. The 1-2-3 conjecture states that $\chi_\Sigma^e(G) \le 3$ for any graph $G$.
The conjecture is confirmed in a case of paths, cycles, bipartite graphs, $3$-colourable graphs and complete graphs. We present the so called 1-2-3-4-5 theorem which states that $\chi_\Sigma^e(G) \le 5$ for any graph $G$. In the case of regular graphs, the result can be improved. It can be show that $\chi_\Sigma^e(G) \le 4$ for any regular graphs. We also analyse asymptotic behaviour of the parameter on random graphs. Results for the total and list version of the problem are also presented.
We developed and analysed an algorithm which for a given graph $G$ constructs an edge weighting for $k=3$ if such a weighting exists.
|
