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ę "edge colouring" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-16 z 16
    Tytuł:
    A note on M2-edge colorings of graphs
    Autorzy:
    Czap, J.
    Powiązania:
    https://bibliotekanauki.pl/articles/255532.pdf
    Data publikacji:
    2015
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    edge colouring
    graph
    Opis:
    An edge coloring φ of a graph G is called an M2-edge coloring if [formula] every vertex v of G, where φ(v) is the set of colors of edges incident with v. Let K2(G) denote the maximum number of colors used in an M2-edge coloring of G. Let G1, G2 and G3 be graphs such that G1 ⊆ G2 ⊆ G3. In this paper we deal with the following question: Assuming that K2(G1) = K2(G3), does it hold K2(G1) = K2(G2) = K2(G3)?
    Źródło:
    Opuscula Mathematica; 2015, 35, 3; 287-291
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Graphs with rainbow connection number two
    Autorzy:
    Kemnitz, Arnfried
    Schiermeyer, Ingo
    Powiązania:
    https://bibliotekanauki.pl/articles/743883.pdf
    Data publikacji:
    2011
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge colouring
    rainbow colouring
    rainbow connection
    Opis:
    An edge-coloured graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow connected. In this paper we prove that rc(G) = 2 for every connected graph G of order n and size m, where $\binom{n-1}{2} + 1 ≤ m ≤ \binom{n}{2} - 1$. We also characterize graphs with rainbow connection number two and large clique number.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2011, 31, 2; 313-320
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A note on the vertex-distinguishing index for some cubic graphs
    Autorzy:
    Taczuk, K.
    Woźniak, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/2050799.pdf
    Data publikacji:
    2004
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    edge colouring
    vertex-distinguishing colouring
    cubic graphs
    Opis:
    The vertex-distinguishing index of a graph G (vdi (G)) is the minimum number of colours required to colour properly the edges of a graph in such a way that any two vertices are incident with different sets of colours. We consider this parameter for some families of cubic graphs.
    Źródło:
    Opuscula Mathematica; 2004, 24, 2; 223-229
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On Fibonacci numbers in edge coloured trees
    Autorzy:
    Bednarz, U.
    Bród, D.
    Szynal-Liana, A.
    Włoch, I.
    Wołowiec-Musiał, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/254765.pdf
    Data publikacji:
    2017
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    edge colouring
    tree
    tripod
    Fibonacci numbers
    Opis:
    In this paper we show the applications of the Fibonacci numbers in edge coloured trees. We determine the second smallest number of all (A, 2B)-edge colourings in trees. We characterize the minimum tree achieving this second smallest value.
    Źródło:
    Opuscula Mathematica; 2017, 37, 4; 479-490
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the Palette Index of Complete Bipartite Graphs
    Autorzy:
    Horňák, Mirko
    Hudák, Juraj
    Powiązania:
    https://bibliotekanauki.pl/articles/31342323.pdf
    Data publikacji:
    2018-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge colouring
    palette index
    bipartite graph
    Opis:
    The palette of a vertex x of a graph G determined by a proper edge colouring φ of G is the set {φ(xy) : xy ∈ E(G)} and the diversity of φ is the number of different palettes determined by φ. The palette index of G is the minimum of diversities of φ taken over all proper edge colourings φ of G. In the article we determine the palette index of Km,n for m ≤ 5 and pose two conjectures concerning the palette index of complete bipartite graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 2; 463-476
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On generating snarks
    Autorzy:
    Chisala, Busiso
    Powiązania:
    https://bibliotekanauki.pl/articles/744213.pdf
    Data publikacji:
    1998
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    snarks
    cubic graphs
    sirth
    edge colouring
    Opis:
    We discuss the construction of snarks (that is, cyclically 4-edge connected cubic graphs of girth at least five which are not 3-edge colourable) by using what we call colourable snark units and a welding process.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1998, 18, 2; 147-158
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Note about sequences of extrema \((A,2B)\)-edge coloured trees
    Autorzy:
    Bednarz, Urszula
    Włoch, Iwona
    Powiązania:
    https://bibliotekanauki.pl/articles/747039.pdf
    Data publikacji:
    2017
    Wydawca:
    Uniwersytet Marii Curie-Skłodowskiej. Wydawnictwo Uniwersytetu Marii Curie-Skłodowskiej
    Tematy:
    Edge colouring
    trees
    Fibonacci numbers
    telephone numbers
    Opis:
    In this paper we determine successive extremal trees with respect to the number of all \((A,2B)\)-edge colourings.
    Źródło:
    Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica; 2017, 71, 2
    0365-1029
    2083-7402
    Pojawia się w:
    Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Fibonacci and Telephone Numbers in Extremal Trees
    Autorzy:
    Bednarz, Urszula
    Włoch, Iwona
    Powiązania:
    https://bibliotekanauki.pl/articles/31342435.pdf
    Data publikacji:
    2018-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge colouring
    tripod
    Fibonacci numbers
    telephone numbers
    Opis:
    In this paper we shall show applications of the Fibonacci numbers in edge-coloured trees. In particular we determine the successive extremal graphs in the class of trees with respect to the number of (A, 2B)-edge colourings. We show connections between these numbers and Fibonacci numbers as well as the telephone numbers.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 1; 121-133
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Forbidden Structures for Planar Perfect Consecutively Colourable Graphs
    Autorzy:
    Borowiecka-Olszewska, Marta
    Drgas-Burchardt, Ewa
    Powiązania:
    https://bibliotekanauki.pl/articles/31341980.pdf
    Data publikacji:
    2017-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge colouring
    consecutive (interval) colouring
    deficiency
    Sevastjanov graph
    forbidden graph
    Opis:
    A consecutive colouring of a graph is a proper edge colouring with posi- tive integers in which the colours of edges incident with each vertex form an interval of integers. The idea of this colouring was introduced in 1987 by Asratian and Kamalian under the name of interval colouring. Sevast- janov showed that the corresponding decision problem is NP-complete even restricted to the class of bipartite graphs. We focus our attention on the class of consecutively colourable graphs whose all induced subgraphs are consecutively colourable, too. We call elements of this class perfect consecutively colourable to emphasise the conceptual similarity to perfect graphs. Obviously, the class of perfect consecutively colourable graphs is induced hereditary, so it can be characterized by the family of induced forbidden graphs. In this work we give a necessary and sufficient conditions that must be satisfied by the generalized Sevastjanov rosette to be an induced forbid- den graph for the class of perfect consecutively colourable graphs. Along the way, we show the exact values of the deficiency of all generalized Sevastjanov rosettes, which improves the earlier known estimating result. It should be mentioned that the deficiency of a graph measures its closeness to the class of consecutively colourable graphs. We motivate the investigation of graphs considered here by showing their connection to the class of planar perfect consecutively colourable graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 2; 315-336
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On odd and semi-odd linear partitions of cubic graphs
    Autorzy:
    Fouquet, Jean-Luc
    Thuillier, Henri
    Vanherpe, Jean-Marie
    Wojda, Adam
    Powiązania:
    https://bibliotekanauki.pl/articles/743181.pdf
    Data publikacji:
    2009
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Cubic graph
    linear arboricity
    strong matching
    edge-colouring
    Opis:
    A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition.
    In this paper we consider linear partitions of cubic simple graphs for which it is well known that la(G) = 2. A linear partition $L = (L_B,L_R)$ is said to be odd whenever each path of $L_B ∪ L_R$ has odd length and semi-odd whenever each path of $L_B$ (or each path of $L_R$) has odd length.
    In [2] Aldred and Wormald showed that a cubic graph G is 3-edge colourable if and only if G has an odd linear partition. We give here more precise results and we study moreover relationships between semi-odd linear partitions and perfect matchings.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2009, 29, 2; 275-292
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On k-intersection edge colourings
    Autorzy:
    Muthu, Rahul
    Narayanan, N.
    Subramanian, C.
    Powiązania:
    https://bibliotekanauki.pl/articles/744421.pdf
    Data publikacji:
    2009
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph theory
    k-intersection edge colouring
    probabilistic method
    Opis:
    We propose the following problem. For some k ≥ 1, a graph G is to be properly edge coloured such that any two adjacent vertices share at most k colours. We call this the k-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the k-intersection chromatic index and is denoted χ'ₖ(G). Let fₖ be defined by
    $fₖ(Δ) = max_{G : Δ(G) = Δ} {χ'ₖ(G)}$.
    We show that fₖ(Δ) = Θ(Δ²/k). We also discuss some open problems.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2009, 29, 2; 411-418
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Critical and Flow-Critical Snarks Coincide
    Autorzy:
    Máčajová, Edita
    Škoviera, Martin
    Powiązania:
    https://bibliotekanauki.pl/articles/32083890.pdf
    Data publikacji:
    2021-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    nowhere-zero flow
    edge-colouring
    cubic graph
    snark
    Opis:
    Over the past twenty years, critical and bicritical snarks have been appearing in the literature in various forms and in different contexts. Two main variants of criticality of snarks have been studied: criticality with respect to the non-existence of a 3-edge-colouring and criticality with respect to the non-existence of a nowhere-zero 4-flow. In this paper we show that these two kinds of criticality coincide, thereby completing previous partial results of de Freitas et al. [Electron. Notes Discrete Math. 50 (2015) 199–204] and Fiol et al. [Electron. J. Combin. 25 (2017) #P4.54].
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 2; 503-511
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On locally irregular decompositions of subcubic graphs
    Autorzy:
    Baudon, O.
    Bensmail, J.
    Hocquard, H.
    Senhaji, M.
    Sopena, E.
    Powiązania:
    https://bibliotekanauki.pl/articles/254905.pdf
    Data publikacji:
    2018
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    locally irregular edge-colouring irregular chromatic index
    subcubic graphs
    Opis:
    A graph G is locally irregular if every two adjacent vertices of G have different degrees. A locally irregular decomposition of G is a partition E1,.. . , Ek of E(G) such that each G[Ei] is locally irregular. Not all graphs admit locally irregular decompositions, but for those who are decomposable, in that sense, it was conjectured by Baudon, Bensmail, Przybyło and Woźniak that they decompose into at most 3 locally irregular graphs. Towards that conjecture, it was recently proved by Bensmail, Merker and Thomassen that every decomposable graph decomposes into at most 328 locally irregular graphs. We here focus on locally irregular decompositions of subcubic graphs, which form an important family of graphs in this context, as all non-decomposable graphs are subcubic. As a main result, we prove that decomposable subcubic graphs decompose into at most 5 locally irregular graphs, and only at most 4 when the maximum average degree is less than 12/5. We then consider weaker decompositions, where subgraphs can also include regular connected components, and prove the relaxations of the conjecture above for subcubic graphs.
    Źródło:
    Opuscula Mathematica; 2018, 38, 6; 795-817
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On Small Balanceable, Strongly-Balanceable and Omnitonal Graphs
    Autorzy:
    Caro, Yair
    Lauri, Josef
    Zarb, Christina
    Powiązania:
    https://bibliotekanauki.pl/articles/32222540.pdf
    Data publikacji:
    2022-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge-colouring
    zero-sum Ramsey
    balanceable graphs
    omnitonal graphs
    Opis:
    In Ramsey Theory for graphs we are given a graph G and we are required to find the least n0 such that, for any n ≥ n0, any red/blue colouring of the edges of Kn gives a subgraph G all of whose edges are blue or all are red. Here we shall be requiring that, for any red/blue colouring of the edges of Kn, there must be a copy of G such that its edges are partitioned equally as red or blue (or the sizes of the colour classes differs by one in the case when G has an odd number of edges). This introduces the notion of balanceable graphs and the balance number of G which, if it exists, is the minimum integer bal(n, G) such that, for any red/blue colouring of E(Kn) with more than bal(n, G) edges of either colour, Kn will contain a balanced coloured copy of G as described above. The strong balance number sbal(n, G) is analogously defined when G has an odd number of edges, but in this case we require that there are copies of G with both one more red edge and one more blue edge. These parameters were introduced by Caro, Hansberg and Montejano. These authors also introduce the more general omnitonal number ot(n, G) which requires copies of G containing a complete distribution of the number of red and blue edges over E(G). In this paper we shall catalogue bal(n, G), sbal(n, G) and ot(n, G) for all graphs G on at most four edges. We shall be using some of the key results of Caro et al. which we here reproduce in full, as well as some new results which we prove here. For example, we shall prove that the union of two bipartite graphs with the same number of edges is always balanceable.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1219-1235
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Proper Rainbow Connection Number of Graphs
    Autorzy:
    Doan, Trung Duy
    Schiermeyer, Ingo
    Powiązania:
    https://bibliotekanauki.pl/articles/32222687.pdf
    Data publikacji:
    2021-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge-colouring
    rainbow connection number
    proper rainbow connection number
    Opis:
    A path in an edge-coloured graph is called a rainbow path if its edges receive pairwise distinct colours. An edge-coloured graph is said to be rainbow connected if any two distinct vertices of the graph are connected by a rainbow path. The minimum k for which there exists such an edge-colouring is the rainbow connection number rc(G) of G. Recently, Bau et al. [Rainbow connectivity in some Cayley graphs, Australas. J. Combin. 71 (2018) 381–393] introduced this concept with the additional requirement that the edge-colouring must be proper. The proper rainbow connection number of G, denoted by prc(G), is the minimum number of colours needed in order to make it properly rainbow connected. Obviously, prc(G) ≥ max{rc(G), χ′(G)}. In this paper we first prove an improved upper bound prc(G) ≤ n for every connected graph G of order n ≥ 3. Next we show that the difference prc(G) – max{rc(G), χ′(G)} can be arbitrarily large. Finally, we present several sufficient conditions for graph classes satisfying prc(G) = χ′(G).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 3; 809-826
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Fan-Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks
    Autorzy:
    Formanowicz, P.
    Tanaś, K.
    Powiązania:
    https://bibliotekanauki.pl/articles/331003.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Oficyna Wydawnicza
    Tematy:
    graf sześcienny
    kolorowanie krawędzi
    skojarzenie doskonałe
    algorytm zrandomizowany
    sieć komputerowa
    cubic graph
    edge colouring
    perfect matching
    randomized algorithms
    computer networks
    Opis:
    It was conjectured by Fan and Raspaud (1994) that every bridgeless cubic graph contains three perfect matchings such that every edge belongs to at most two of them. We show a randomized algorithmic way of finding Fan-Raspaud colorings of a given cubic graph and, analyzing the computer results, we try to find and describe the Fan-Raspaud colorings for some selected classes of cubic graphs. The presented algorithms can then be applied to the pair assignment problem in cubic computer networks. Another possible application of the algorithms is that of being a tool for mathematicians working in the field of cubic graph theory, for discovering edge colorings with certain mathematical properties and formulating new conjectures related to the Fan-Raspaud conjecture.
    Źródło:
    International Journal of Applied Mathematics and Computer Science; 2012, 22, 3; 765-778
    1641-876X
    2083-8492
    Pojawia się w:
    International Journal of Applied Mathematics and Computer Science
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-16 z 16

      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