Search results for: GRAFY KUBICZNE

• Packing Three-Vertex Paths in 2-Connected Cubic Graphs

  Publication

  • A. Kosowski
  • P. Żyliński

  - ARS COMBINATORIA - Year 2008

  W pracy rozważano problem rozmieszczanie ścieżek P3 w 2-spójnych grafach 3-regularnych. Pokazano, że w 2-spójnym grafie 3-regularnym o n wierzchołkach można zawsze pokryć 9/11 n wierzchołków przez ścieżki P3; podano także odpowiednie oszacowania górne.

  Full text to download in external service

• Tighter bounds on the size of a maximum P3-matching in a cubic graph

  Publication

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

  - GRAPHS AND COMBINATORICS - Year 2008

  W pracy pokazano, że największe P3-skojarzenie dla dowolnego grafu o n>16 wierzchołkach składa się z przynajmniej 117n/152 wierzchołków.

  Full text to download in external service

• Sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych

  Publication

  • H. Furmańczyk
  • M. Kubale

  - Year 2014

  W pracy rozpatrywane są sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych. Pokazano, że w odróżnieniu od tego pierwszego, który jest łatwy, problem istnienia pokolorowań półsprawiedliwych jest NP-zupełny w szerokim zakresie parametrów grafów.