Search results for: THORNY GRAPHS

• The computational complexity of the backbone coloring problem for planar graphs with connected backbones

  Publication

  • R. Janczewski
  • K. Turowski

  - DISCRETE APPLIED MATHEMATICS - Year 2015

  In the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...

  Full text available to download

• 2-Coloring number revisited

  Publication

  • R. Janczewski
  • P. Obszarski
  • K. Turowski

  - THEORETICAL COMPUTER SCIENCE - Year 2019

  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...

  Full text available to download