- Tytuł:
- On Incidence Coloring of Complete Multipartite and Semicubic Bipartite Graphs
- Autorzy:
-
Janczewski, Robert
Małafiejski, Michał
Małafiejska, Anna - Powiązania:
- https://bibliotekanauki.pl/articles/31342434.pdf
- Data publikacji:
- 2018-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
incidence coloring
complete multipartite graphs
semicubic graphs
subcubic graphs
-completeness
L (1,1)-labelling - Opis:
- In the paper, we show that the incidence chromatic number $ \chi_i $ of a complete $k$-partite graph is at most $ \Delta + 2 $ (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to $ \Delta + 1 $ if and only if the smallest part has only one vertex (i.e., $ \Delta = n − 1 $). Formally, for a complete k-partite graph $ G = K_{r_1,r_2,...,r_k} $ with the size of the smallest part equal to $ r_1 \ge 1 $ we have $$ \chi_i (G)= \begin{cases} \Delta(G)+1 & \text { if } r_1=1, \\ \Delta(G)+2 & \text { if } r_1>1. \end{cases} $$ In the paper we prove that the incidence 4-coloring problem for semicubic bipartite graphs is \( \mathcal{NP} \)-complete, thus we prove also the \( \mathcal{NP} \)-completeness of L(1, 1)-labeling problem for semicubic bipartite graphs. Moreover, we observe that the incidence 4-coloring problem is \( \mathcal{NP} \)-complete for cubic graphs, which was proved in the paper [12] (in terms of generalized dominating sets).
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 107-119
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł