PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wynik贸w
2017 | 38 | 1 | 107-119
Tytu艂 artyku艂u

On Incidence Coloring of Complete Multipartite and Semicubic Bipartite Graphs

Tre艣膰 / Zawarto艣膰
Warianty tytu艂u
J臋zyki publikacji
EN
Abstrakty
EN
In the paper, we show that the incidence chromatic number 蠂i 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 (i.e., 螖 = n 鈭 1). Formally, for a complete k-partite graph G = Kr1,r2,...,rk with the size of the smallest part equal to r1 鈮 1 we have 蠂i(G)={螖(G)+1if鈥塺1=1,螖(G)+2if鈥塺1>1. $$\chi _i (G) = \left\{ {\matrix{{\Delta (G) + 1} & {{\rm{if}}\;r_1 = 1,} \cr {\Delta (G) + 2} & {{\rm{if}}\;r_1 > 1.} \cr } } \right.$$ In the paper we prove that the incidence 4-coloring problem for semicubic bipartite graphs is 饾挬饾挮-complete, thus we prove also the 饾挬饾挮-completeness of L(1, 1)-labeling problem for semicubic bipartite graphs. Moreover, we observe that the incidence 4-coloring problem is 饾挬饾挮-complete for cubic graphs, which was proved in the paper [12] (in terms of generalized dominating sets).
Wydawca
Rocznik
Tom
38
Numer
1
Strony
107-119
Opis fizyczny
Daty
wydano
2018-02-01
otrzymano
2016-03-08
poprawiono
2016-10-07
zaakceptowano
2016-10-14
online
2017-12-30
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1995
JavaScript jest wy艂膮czony w Twojej przegl膮darce internetowej. W艂膮cz go, a nast臋pnie od艣wie偶 stron臋, aby m贸c w pe艂ni z niej korzysta膰.