Temat: 1, 2, 3-Conjecture - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: The 1,2,3-Conjecture and 1,2-Conjecture for sparse graphs
Autorzy:: Cranston, Daniel W.
Jahanbekam, Sogol
West, Douglas B.
Tematy:: reducible configuration
discharging method
1, 2, 3-Conjecture
1, 2-Conjecture; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/30148718.pdf Link otwiera się w nowym oknie
Opis:: The 1, 2, 3-Conjecture states that the edges of a graph without isolated edges can be labeled from {1, 2, 3} so that the sums of labels at adjacent vertices are distinct. The 1, 2-Conjecture states that if vertices also receive labels and the vertex label is added to the sum of its incident edge labels, then adjacent vertices can be distinguished using only {1, 2}. We show that various configurations cannot occur in minimal counterexamples to these conjectures. Discharging then confirms the conjectures for graphs with maximum average degree less than 8/3. The conjectures are already confirmed for larger families, but the structure theorems and reducibility results are of independent interest.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Artykuł

Skocz do pozycji: 3.

Tytuł:: On {a, b}-Edge-Weightings of Bipartite Graphs with Odd a, b
Autorzy:: Bensmail, Julien
Inerney, Fionn Mc
Lyngsie, Kasper Szabo
Tematy:: neighbour-sum-distinguishing edge-weightings
bipartite graphs
odd weights
1-2-3 Conjecture; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32361745.pdf Link otwiera się w nowym oknie
Opis:: For any S ⊂ ℤ we say that a graph G has the S-property if there exists an S-edge-weighting w : E(G) → S such that for any pair of adjacent vertices u, v we have ∑_e∈E(v) w(e) ≠ ∑_e∈E(u) w(e), where E(v) and E(u) are the sets of edges incident to v and u, respectively. This work focuses on {a, a+2}-edge-weightings where a ∈ ℤ is odd. We show that a 2-connected bipartite graph has the {a, a+2}-property if and only if it is not a so-called odd multi-cactus. In the case of trees, we show that only one case is pathological. That is, we show that all trees have the {a, a+2}-property for odd a ≠ −1, while there is an easy characterization of trees without the {−1, 1}-property.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: On a graph labelling conjecture involving coloured labels
Autorzy:: Bensmail, Julien
Tematy:: proper labelling
coloured label
Weak $(2,2)$-Conjecture
1-2-3 Conjecture; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59882204.pdf Link otwiera się w nowym oknie
Opis:: In this work, we investigate a recent conjecture by Baudon, Bensmail, Davot, Hocquard, Przybyło, Senhaji, Sopena and Woźniak, which states that graphs, in general, can be edge-labelled with red labels $1,2$ and blue labels $1,2$ so that every two adjacent vertices are distinguished accordingly to either the sums of their incident red labels or the sums of their incident blue labels. To date, this was verified for several classes of graphs. Also, it is known how to design several labelling schemes that are very close to what is desired. In this work, we adapt two important proofs of the field, leading to some progress towards that conjecture. We first prove that graphs can be labelled with red labels $1,2,3$ and blue labels $1,2$ so that every two adjacent vertices are distinguished as required. We then verify the conjecture for graphs with chromatic number at most $4$.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 5.

Tytuł:: An Oriented Version of the 1-2-3 Conjecture
Autorzy:: Baudon, Olivier
Bensmail, Julien
Sopena, Éric
Tematy:: oriented graph
neighbour-sum-distinguishing arc-weighting
complexity
1-2-3 Conjecture; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31339138.pdf Link otwiera się w nowym oknie
Opis:: The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph $G$ with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of $G$. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph $\overrightarrow{G}$ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of $\overrightarrow{G}$ receive distinct sums of outgoing weights. This result is tight in the sense that some oriented graphs do not admit such an assignment using the weights from {1, 2} only. We finally prove that deciding whether two weights are sufficient for a given oriented graph is an $\mathsf{NP}$-complete problem. These results also hold for product or list versions of this problem.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 6.

Tytuł:: Maximising 1’s through proper labellings
Autorzy:: Bensmail, Julien
Tematy:: proper labelling
incident sum
label~$1$
1-2-3 conjecture; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59945820.pdf Link otwiera się w nowym oknie
Opis:: We investigate graph proper labellings, i.e., assignments of labels to the edges so that no two adjacent vertices are incident to the same sum of labels, with the additional requirement that label $1$ must be assigned to as many edges as possible. The study of such objects is motivated by practical concerns, and by connections with other types of proper labellings in which other additional properties (such as minimising the sum of assigned labels, or minimising the use of label $3$) must be met. We prove that maximising $1$'s is a problem on its own, in that it is not equivalent to any of these other labelling problems with optimisation concerns. We then provide labelling tools and techniques for designing proper labellings with many $1$'s. As a result, we prove that, for several graph classes, it is always possible to design proper labellings where label $1$ is assigned to about half the edges.
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja