Temat: discharging method - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: Domination Number of Graphs with Minimum Degree Five
Autorzy:: Bujtás, Csilla
Tematy:: dominating set
domination number
discharging method; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32222697.pdf Link otwiera się w nowym oknie
Opis:: We prove that for every graph G on n vertices and with minimum degree five, the domination number γ(G) cannot exceed n/3. The proof combines an algorithmic approach and the discharging method. Using the same technique, we provide a shorter proof for the known upper bound 4n/11 on the domination number of graphs of minimum degree four.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: On Edge Colorings of 1-Planar Graphs without 5-Cycles with Two Chords
Autorzy:: Sun, Lin
Wu, Jianliang
Tematy:: 1-planar graphs
edge coloring
discharging method; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31343454.pdf Link otwiera się w nowym oknie
Opis:: A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that every 1-planar graph with maximum degree ∆ ≥ 8 is edge-colorable with ∆ colors if each of its 5-cycles contains at most one chord.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: Neighbor Sum Distinguishing Total Chromatic Number of Planar Graphs without 5-Cycles
Autorzy:: Zhao, Xue
Xu, Chang-Qing
Tematy:: neighbor sum distinguishing total coloring
discharging method
planar graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32083807.pdf Link otwiera się w nowym oknie
Opis:: For a given graph $ G = (V (G), E(G)) $, a proper total coloring $ \phi : V (G) \cup E(G) $ $ \rightarrow {1, 2, . . ., k} $ is neighbor sum distinguishing if $ f(u) \ne f(v) $ for each edge $ uv \in E(G) $, where $ f(v) = \Sigma_{ uv \in E(G) } $ $ \phi (uv) + \phi (v) $, $ v \in V (G) $. The smallest integer $k$ in such a coloring of $G$ is the neighbor sum distinguishing total chromatic number, denoted by $ \chi_\Sigma^{''} (G) $. Pilśniak and Woźniak first introduced this coloring and conjectured that $ \chi_\Sigma^{''}(G) \le \Delta (G)+3 $ for any graph with maximum degree $ \Delta (G) $. In this paper, by using the discharging method, we prove that for any planar graph $G$ without 5-cycles, $ \chi_\Sigma^{''} (G) \le \text{max} \{ \Delta (G)+2, 10 \} $. The bound $ \Delta (G) + 2 $ is sharp. Furthermore, we get the exact value of $ \chi_\Sigma^{''} (G) $ if $ \Delta (G) \ge 9 $.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Additive List Coloring of Planar Graphs with Given Girth
Autorzy:: Brandt, Axel
Jahanbekam, Sogol
White, Jennifer
Tematy:: lucky labeling
additive coloring
reducible configuration
discharging method
Combinatorial Nullstellensatz; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31525335.pdf Link otwiera się w nowym oknie
Opis:: An additive coloring of a graph G is a labeling of the vertices of G from {1, 2, . . ., k} such that two adjacent vertices have distinct sums of labels on their neighbors. The least integer k for which a graph G has an additive coloring is called the additive coloring number of G, denoted χ_Σ (G). Additive coloring is also studied under the names lucky labeling and open distinguishing. In this paper, we improve the current bounds on the additive coloring number for particular classes of graphs by proving results for a list version of additive coloring. We apply the discharging method and the Combinatorial Nullstellensatz to show that every planar graph G with girth at least 5 has χ_Σ (G) ≤ 19, and for girth at least 6, 7, and 26, χ_Σ (G) is at most 9, 8, and 3, respectively. In 2009, Czerwiński, Grytczuk, and Żelazny conjectured that χ_Σ (G) ≤ χ(G), where χ(G) is the chromatic number of G. Our result for the class of non-bipartite planar graphs of girth at least 26 is best possible and affirms the conjecture for this class of graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

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ł

na półce

Skocz do pozycji: 6.

Tytuł:: Adjacent vertex strongly distinguishing total coloring of graphs with lower average degree
Autorzy:: Wen, Fei
Zhou, Li
Li, Zepeng
Tematy:: adjacent vertex strongly distinguishing total-coloring
adjacent
vertex strongly distinguishing total chromatic number
maximum average
degree
discharging method; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59950941.pdf Link otwiera się w nowym oknie
Opis:: An adjacent vertex strongly distinguishing total-coloring of a graph $G$ is a proper total-coloring such that no two adjacent vertices meet the same color set, where the color set of a vertex consists of all colors assigned on the vertex and its incident edges and neighbors. The minimum number of the colors required is called adjacent vertex strongly distinguishing total chromatic number, denoted by $ \chi_{ast}(G) $. Let $ \text{mad}(G)$ and $\Delta(G)$ denote the maximum average degree and the maximum degree of graph $G$, respectively. In this paper, we prove the following results. (1) If $G$ is a graph with $ \text{mad}(G) < \tfrac{7}{3} $ and $\Delta(G)\geq5$, then $ \chi_{ast}(G) \leq\max\{\Delta(G)+2, 8\} $. (2) If $G$ is a graph with $ \text{mad}(G) < \tfrac{9}{4} $ and $4\leq\Delta(G)\leq5$, then $ \chi_{ast}(G)\leq\Delta(G)+2 $. (3) If $G$ is a graph with $ \text{mad}(G) <\tfrac{9}{4} $ and $\Delta(G)=3$, then $ \chi_{ast}(G)\leq6 $.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 7.

Tytuł:: Hipoteza Wegnera - kolorowanie kwadratu grafu planarnego.
Wegners conjecture - coloring the square of a planar graph
Autorzy:: Byczek, Rafał
Opis:: In this paper, we present the current state of knowledge about the Wegner’s conjecture, i.e. the conjecture regarding the minimum number of colors needed to properly color the vertex of the square of a planar graph depending on the maximum vertex degree of this graph. Our main goal was to collect and organize numerous results from the point of view of the proof methods used in them. In the course of writing this paper, we tried to look at the material together to capture the main high-level thoughts that have been developed many times by successive authors. These are mainly a discharging method and a decomposition method. In particular, we focused on precisely presenting the best results in this area and showing the relationships between them. We present here, inter alia, two significantly different proofs of the Wegner’s conjecture in the case when ∆ ≤ 3 and the currently asymptotically best result in the general case, which leads to a quadratic algorithm finding the appropriate coloring. This paper ends with a concise summary and characterization of the problems that still remain open on this subject.
W niniejszej pracy przedstawimy aktualny stan wiedzy na temat hipotezy Wegnera, czyli hipotezy dotyczącej minimalnej liczby kolorów potrzebnych do poprawnego pokolorowania wierzchołkowego kwadratu grafu planarnego w zależności od maksymalnego stopnia wierzchołka tego grafu. Naszym głównym celem było zebranie i uporządkowanie licznych rezultatów z punktu widzenia technik dowodowych jakie są w nich stosowane. W trakcie powstawania tej pracy próbowaliśmy spojrzeć na materiał łącznie, aby uchwycić główne wysokopoziomowe myśli, które wielokrotnie były rozwijane przez kolejnych autorów. Są to głównie metoda rozładowania (discharging method) oraz metoda dekompozycji. W szczególności zajęliśmy się precyzyjnym przedstawieniem najlepszych obecnie wyników w tej tematyce i ukazaniem związków pomiędzy nimi. Prezentujemy tutaj między innymi dwa istotnie różne dowody hipotezy Wegnera w przypadku, gdy ∆ ≤ 3 oraz aktualnie najlepszy asymptotycznie wynik w przypadku ogólnym, który prowadzi do kwadratowego algorytmu znajdującego odpowiednie kolorowanie. Pracę wieńczy zwięzłe podsumowanie oraz charakteryzacja problemów, które w tej tematyce wciąż pozostają otwarte.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Informacja

Wyszukujesz frazę "discharging method" wg kryterium: Temat