Wyniki wyszukiwania dla: ORDERED COLOURING

• ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS

  Czasopisma

  ISSN: 0167-8094 , eISSN: 1572-9273

• Minimum order of graphs with given coloring parameters

  Publikacja

  • G. Bacsó
  • P. Borowiecki
  • M. Hujter
  • Z. Tuza

  - DISCRETE MATHEMATICS - Rok 2015

  A complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),...

  Pełny tekst do pobrania w portalu

• Parity vertex colouring of graphs

  Publikacja

  • P. Borowiecki
  • K. Budajova
  • S. Jendrol
  • S. Krajci

  - Discussiones Mathematicae Graph Theory - Rok 2011

  A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let Xp(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds X(G) <= Xp(G) <=|V(G)|− a(G)+1, where X(G) and a(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for...

  Pełny tekst do pobrania w portalu

• On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs

  Publikacja

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

  - Discussiones Mathematicae Graph Theory - Rok 2018

  In the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.

  Pełny tekst do pobrania w portalu

• Equitable coloring of hypergraphs

  Publikacja

  • H. Furmańczyk
  • P. Obszarski

  - DISCRETE APPLIED MATHEMATICS - Rok 2019

  A hypergraph is equitablyk-colorable if its vertices can be partitioned into k sets/colorclasses in such a way that monochromatic edges are avoided and the number of verticesin any two color classes differs by at most one. We prove that the problem of equitable 2-coloring of hypergraphs is NP-complete even for 3-uniform hyperstars. Finally, we apply the method of dynamic programming for designing a polynomial-time algorithm to...

  Pełny tekst do pobrania w portalu

• Rank Coloring of Graphs.

  Publikacja

  • D. Dereniowski

  - Rok 2004

  Rozdział jest poświęcony uporządkowanemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.

• Harmonions Coloring of Graphs.

  Publikacja

  • M. Kubale

  - Rok 2004

  Problem kolorowania grafów jest motywowany radionawigacją lotniczą, kompresją obrazów i in. W rozdziale podano podstawowe fakty dotyczące tego modelu kolorowania, a wsród nich dolne i górne oszacowania na liczbę harmoniczną i algorytm o złożoności 0 (mm3) dający bardzo dobre pokolorowania przybliżone.

• T-coloring of graphs.

  Publikacja

  • R. Janczewski

  - Rok 2004

  Niniejszy rozdział omawia kontrastowe kolorowanie grafów. Podana została jego definicja i podstawowe własności, zastosowania oraz złożoność obliczeniowa problemów rozważanych w ramach tej dziedziny.

• Classical coloring of graphs.

  Publikacja

  • A. Kosowski
  • K. Manuszewski

  - Rok 2004

  Rozdział obejmuje klasyczne kolorowanie krawędzi i wierzołków w grafach prostych. Oprócz podstawowych definicji podane zostały najczęściej stosowane metody przybliżone oraz ich właściwości. Dodatkowo rozdział zawiera przegląd znanych benczmarków dla podanych metod w kontekście klasycznego modelu kolorowania.

• Sum Coloring of Graphs.

  Publikacja

  • M. Małafiejski

  - Rok 2004

  Rozdział jest poświęcony sumacyjnemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.