Search results for: subcubic graphs

• On the hardness of computing span of subcubic graphs

  Publication

  • R. Janczewski
  • K. Turowski

  - INFORMATION PROCESSING LETTERS - Year 2016

  In the paper we study the problem of finding ξ-colorings with minimal span, i.e. the difference between the largest and the smallest color used.

  Full text to download in external service

• Interval incidence coloring of subcubic graphs

  Publication

  • A. Małafiejska
  • M. Małafiejski

  - Discussiones Mathematicae Graph Theory - Year 2017

  In this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is N P-complete, and they asked if χii(G) ≤ 2∆(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with ∆(G) = 3.

  Full text available to download

• An approximation algorithm for maximum P3-packing in subcubic graphs

  Publication

  • A. Kosowski
  • M. Małafiejski
  • P. Żyliński

  - INFORMATION PROCESSING LETTERS - Year 2006

  W pracy podano algorytm 4/3-przyliżony dla trudnego obliczeniowo problemu umieszczania wierzchołkowo rozłącznych dwukrawędziowych ścieżek w grafach o stopniu maksymalnym 3 i stopniu minimalnym 2. Poprawiono tym samym wcześniejsze wyniki dla grafów kubicznych (A. Kelmans, D. Mubayi, Journal of Graph Theory 45, 2004).

  Full text to download in external service

• Packing three-vertex paths in a subcubic graph

  Publication

  • A. Kosowski
  • M. Małafiejski
  • P. Żyliński

  - Year 2005

  W pracy rozważany jest problem pakowania scieżek P3 w grafach podkubicznych, pokazano oszacowania dolne na ilość ścieżek w zależności od stopnia spójności grafu oraz minimalnego stopnia.

• Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs

  Publication

  • M. Kubale
  • H. Furmańczyk

  - Year 2016

  In this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.

  Full text to download in external service

• Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs

  Publication

  • H. Furmańczyk
  • M. Kubale

  - DISCRETE APPLIED MATHEMATICS - Year 2018

  We consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.

  Full text available to download

• GRAPHS AND COMBINATORICS

  Journals

  ISSN: 0911-0119 , eISSN: 1435-5914

• Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.

  Publication

  • H. Furmańczyk
  • A. Kosowski
  • P. Żyliński

  - Year 2008

  W pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.

  Full text to download in external service

• Discussiones Mathematicae Graph Theory

  Journals

  ISSN: 1234-3099 , eISSN: 2083-5892

• Connection graphs

  Publication

  • P. Bartłomiejczyk

  - FUNDAMENTA MATHEMATICAE - Year 2006

  Full text to download in external service