Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "maximum average degree" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-5 z 5
    Tytuł:
    Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree
    Autorzy:
    Fiedorowicz, Anna
    Powiązania:
    https://bibliotekanauki.pl/articles/30146851.pdf
    Data publikacji:
    2013-03-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    acyclic colouring
    bounded degree graph
    maximum average degree
    Opis:
    A k-colouring of a graph G is a mapping c from the set of vertices of G to the set {1, . . ., k} of colours such that adjacent vertices receive distinct colours. Such a k-colouring is called acyclic, if for every two distinct colours i and j, the subgraph induced by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, every cycle in G has at least three distinct colours. Acyclic colourings were introduced by Gr¨unbaum in 1973, and since then have been widely studied. In particular, the problem of acyclic colourings of graphs with bounded maximum degree has been investigated. In 2011, Kostochka and Stocker showed that any graph with maximum degree 5 can be acyclically coloured with at most 7 colours. The question, whether this bound is achieved, remains open. In this note we prove that any graph with maximum degree 5 and maximum average degree at most 4 admits an acyclic 6-colouring. We also provide examples of graphs with these properties.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 1; 91-99
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree
    Autorzy:
    Dong, Aijun
    Zhang, Xin
    Powiązania:
    https://bibliotekanauki.pl/articles/31342275.pdf
    Data publikacji:
    2018-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph coloring
    equitable choosability
    maximum average degree
    Opis:
    A graph is said to be equitably $k$-colorable if the vertex set $V (G)$ can be partitioned into $k$ independent subsets $ V_1, V_2, . . ., V_k $ such that $ | | V_i |−| V_j | | \le 1 $ $(1 \le i, j \le k) $. A graph $G$ is equitably $k$-choosable if, for any given $k$-uniform list assignment $L$, $G$ is $L$-colorable and each color appears on at most $ \ceil{ \frac{|V(G)|}{ k } } $ vertices. In this paper, we prove that if $G$ is a graph such that $ mad(G) < 3 $, then $G$ is equitably $k$-colorable and equitably $k$- choosable where $ k \ge \text{max} \{ \Delta (G), 4 \} $. Moreover, if $G$ is a graph such that $ mad(G) < \frac{12}{5} $, then $G$ is equitably $k$-colorable and equitably $k$-choosable where $ k \ge \text{max} \{ \Delta (G), 3 \} $.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 3; 829-839
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Linear List Coloring of Some Sparse Graphs
    Autorzy:
    Chen, Ming
    Li, Yusheng
    Zhang, Li
    Powiązania:
    https://bibliotekanauki.pl/articles/32083756.pdf
    Data publikacji:
    2021-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    linear coloring
    maximum average degree
    planar graphs
    discharging
    Opis:
    A linear $k$-coloring of a graph is a proper $k$-coloring of the graph such that any subgraph induced by the vertices of any pair of color classes is a union of vertex-disjoint paths. A graph $G$ is linearly $L$-colorable if there is a linear coloring $c$ of $G$ for a given list assignment $L = \{L(v) : v ∈ V(G)\}$ such that $c(v) ∈ L(v)$ for all $v ∈ V(G)$, and $G$ is linearly $k$-choosable if $G$ is linearly $L$-colorable for any list assignment with $|L(v)| ≥ k$. The smallest integer $k$ such that $G$ is linearly $k$-choosable is called the linear list chromatic number, denoted by $lc_l(G)$. It is clear that \(lc_l(G)≥\Big\lceil\frac{\Delta(G)}{1}\Big\rceil+1\) for any graph $G$ with maximum degree $\Delta(G)$. The maximum average degree of a graph $G$, denoted by $mad(G)$, is the maximum of the average degrees of all subgraphs of $G$. In this note, we shall prove the following. Let $G$ be a graph, (1) if $mad(G)<\frac{8}{3}$ and $\Delta(G) ≥ 7$, then \(lc_l(G)=\Big\lceil\frac{\Delta(G)}{2}\Big\rceil+1\); (2) if $mad(G)<{18}{7}$ and $\Delta(G) ≥ 5$, then \(lc_l(G)=\Big\lceil\frac{\Delta(G)}{2}\Big\rceil+1\); (3) if $mad(G)<{20}{7}$ and $\Delta(G) ≥ 5$, then \(lc_l(G)≤\Big\lceil\frac{\Delta(G)}{2}\Big\rceil+2\).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 1; 51-64
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Some totally 4-choosable multigraphs
    Autorzy:
    Woodall, Douglas
    Powiązania:
    https://bibliotekanauki.pl/articles/743409.pdf
    Data publikacji:
    2007
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    maximum average degree
    planar graph
    total choosability
    list total colouring
    Opis:
    It is proved that if G is multigraph with maximum degree 3, and every submultigraph of G has average degree at most 2(1/2) and is different from one forbidden configuration C⁺₄ with average degree exactly 2(1/2), then G is totally 4-choosable; that is, if every element (vertex or edge) of G is assigned a list of 4 colours, then every element can be coloured with a colour from its own list in such a way that no two adjacent or incident elements are coloured with the same colour. This shows that the List-Total-Colouring Conjecture, that ch''(G) = χ''(G) for every multigraph G, is true for all multigraphs of this type. As a consequence, if G is a graph with maximum degree 3 and girth at least 10 that can be embedded in the plane, projective plane, torus or Klein bottle, then ch''(G) = χ''(G) = 4. Some further total choosability results are discussed for planar graphs with sufficiently large maximum degree and girth.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2007, 27, 3; 425-455
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Incidence Coloring—Cold Cases
    Autorzy:
    Kardoš, František
    Maceková, Mária
    Mockovčiaková, Martina
    Sopena, Éric
    Soták, Roman
    Powiązania:
    https://bibliotekanauki.pl/articles/32083735.pdf
    Data publikacji:
    2020-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    incidence coloring
    incidence chromatic number
    planar graph
    maximum average degree
    Opis:
    An incidence in a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v, e) and (u, f) are adjacent if at least one of the following holds: (i) v = u, (ii) e = f, or (iii) edge vu is from the set {e, f}. An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. The minimum number of colors needed for incidence coloring of a graph is called the incidence chromatic number. It was proved that at most Δ(G) + 5 colors are enough for an incidence coloring of any planar graph G except for Δ(G) = 6, in which case at most 12 colors are needed. It is also known that every planar graph G with girth at least 6 and Δ(G) ≥ 5 has incidence chromatic number at most Δ(G) + 2. In this paper we present some results on graphs regarding their maximum degree and maximum average degree. We improve the bound for planar graphs with Δ(G) = 6. We show that the incidence chromatic number is at most Δ(G) + 2 for any graph G with mad(G) < 3 and Δ(G) = 4, and for any graph with mad(G)<103 and Δ(G) ≥ 8.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 1; 345-354
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-5 z 5

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies