Robert Janczewski - Publikacje - MOST Wiedzy

Wyszukiwarka

Filtry

wszystkich: 40

  • Kategoria
  • Rok
  • Opcje

wyczyść Filtry wybranego katalogu niedostępne

Katalog Publikacji

Rok 2023
  • Edge coloring of graphs of signed class 1 and 2
    Publikacja

    - DISCRETE APPLIED MATHEMATICS - Rok 2023

    Recently, Behr (2020) introduced a notion of the chromatic index of signed graphs and proved that for every signed graph (G, σ) it holds that ∆(G) ≤ χ′(G,σ) ≤ ∆(G) + 1, where ∆(G) is the maximum degree of G and χ′ denotes its chromatic index. In general, the chromatic index of (G, σ) depends on both the underlying graph G and the signature σ. In the paper we study graphs G for which χ′(G, σ) does not depend on σ. To this aim we...

    Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2022
  • Infinite chromatic games

    In the paper we introduce a new variant of the graph coloring game and a new graph parameter being the result of the new game. We study their properties and get some lower and upper bounds, exact values for complete multipartite graphs and optimal, often polynomial-time strategies for both players provided that the game is played on a graph with an odd number of vertices. At the end we show that both games, the new and the classic...

    Pełny tekst do pobrania w portalu

  • Weighted 2-sections and hypergraph reconstruction
    Publikacja

    In the paper we introduce the notion of weighted 2-sections of hypergraphs with integer weights and study the following hypergraph reconstruction problems: (1) Given a weighted graph , is there a hypergraph H such that is its weighted 2-section? (2) Given a weighted 2-section , find a hypergraph H such that is its weighted 2-section. We show that (1) is NP-hard even if G is a complete graph or integer weights w does not exceed...

    Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2021
Rok 2019
  • 2-Coloring number revisited

    2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow...

    Pełny tekst do pobrania w portalu

Rok 2018
Rok 2016
Rok 2015
Rok 2014
  • Interval incidence coloring of bipartite graphs

    In this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=2Δ holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic...

    Pełny tekst do pobrania w portalu

  • The Backbone Coloring Problem for Small Graphs

    In this paper we investigate the values of the backbone chromatic number, derived from a mathematical model for the problem of minimization of bandwidth in radio networks, for small connected graphs and connected backbones (up to 7 vertices). We study the relationship of this parameter with the structure of the graph and compare the results with the solutions obtained using the classical graph coloring algorithms (LF, IS), modified...

    Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2012
Rok 2011
Rok 2010
Rok 2009
Rok 2007
Rok 2005
Rok 2004
Rok 2003
Rok 2002

wyświetlono 3743 razy