Zwarte końcówkowe kolorowanie grafów

• Autorzy: Janczewski R. , Małafiejska A. , Małafiejski M.

Warianty tytułu

EN

Consecutive incidence coloring of graphs

• Języki publikacji: PL

Abstrakty

PL

W pracy rozważamy nowy model kolorowania grafów, mianowicie zwartego kolorowania końcówek (incydencji) grafu. W klasycznym zwartym kolorowaniu krawędzi grafu staramy się zapewnić, aby zbiór kolorów krawędzi sąsiednich do danego wierzchołka tworzył przedział (zwarty zbiór). Podobny warunek można nałożyć na zbiór kolorów incydencji wychodzących z wierzchołka w końcówkowym kolorowaniu grafu. W pracy, obok zdefiniowania problemu i wskazania potencjalnych zastosowań, wyznaczone zostały oszacowania dolne i górne na wartość szukanego kryterium, ponadto zaproponowane zostały dokładne wartości zwartego końcówkowego indeksu chromatycznego dla wybranych klas grafów: ścieżek, cykli, gwiazd, 2-gwiazd, k-gwiazd, wachlarzy, kół, grafów pełnych, pełnych dwudzielnych oraz pełnych k-dzielnych.

EN

In the paper we present a new model of consecutive incidence graph coloring arising from two previous known models: consecutive (interval) edge coloring and incidence coloring. We formulate the problem and present same applications. We proposed same lower and upper bounds for consecutive incidence chromatic index and constructed polynomial time algorithms solving the problem for same classes of graphs: paths, cycles, stars and k-stars, wheels, fang, complete graphs and complete k-partite graphs.

Słowa kluczowe

PL

zwarte kolorowanie końcówkowe; zbiór zwarty; wartości zwartego końcówkowego indeksu; koła i wachlarze; grafy pełne k-dzielne

EN

consecutive incidence coloring of graphs; consecutive incidence chromatic index; wheels and fang; complete k-partite graphs

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2007
• Tom: T. 13
• Strony: 481--488
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Janczewski R.

autor

Małafiejska A.

autor

Małafiejski M.

• Katedra Algorytmów i Modelowania Systemów, Politechnika Gdańska

Bibliografia

• [1] A1gor I., Alon N.: The star arboricity of graph, Discrete Mathematics 75 (1989) 11-22
• [2] A1on N., McDiarmid C., Reed B.: Star arboricity, Combinatorica 12 (1992), 375-380
• [3] Asratian A., Kamalian R.: Investigation on interval edge-colorings of graphs, J. Combin. Theory, Ser. B 62 (1994), 34-43
• [4] Brua1di R.A., Massey J.Q.: Incidence and strong edge colorings of graphs, Discrete Mathematics 122 (1993) 51-58
• [5] Chen D.L., Liu X.K., Wang S.D.: The incidence chromatic number and the incidence coloring conjecture of graphs, Math. Econom. 15 (3) (1998) 47-51
• [6] Chen D.L., Pang S.C., Wang S.D.: The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Mathematics 256 (2002) 397-405
• [7] Dolama M.H., Sopena E., Zhu X.: Incidence coloring of k-degenerated graphs, Discrete Mathematics 283 (2004),121-128
• [8] Giaro K.: Interval edge-coloring, in: Graph Co1orings (ed. M. Kubale), Contemporary Mathematics, AMS (2004), 105-121
• [9] Giaro K., Kubale M., Małafiejski M.: Consecutive colorings of the edges of general graphs, Discrete Mathemathics 236 (2001),131-143
• [10] Giaro K., Kubale M., Małafiejski M.: Compact scheduling in open shop with zero-one time operations, INFOR 37 (1999) 37-47
• [11] Guidu1i B.: On incidence coloring and star arboricity of graphs, Discrete Mathematics 163 (1997) 275-278
• [12] Janczewski R., Małafiejski M.: Incidence coloring of multitrees, praca zgłoszona na konferencję Techn. Inf. (2007), 1-8
• [13] Shiu W.C., Lam P.C.B., Chen D.-L.: Note on incidence coloring for some cubic graphs, Discrete Mathematics 252 (2002), 259-266