Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: 𝒩𝒫-completeness

Sortuj według:

Ogranicz wyniki do:

On Incidence Coloring of Complete Multipartite and Semicubic Bipartite Graphs

100%

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

Discussiones Mathematicae Graph Theory

2017

tom 38

nr 1

107-119

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 r1=1,Δ(G)+2if r1>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).

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Janczewski R.

1 Małafiejska A.

1 Małafiejski M.

1 2018

Wyniki wyszukiwania

On Incidence Coloring of Complete Multipartite and Semicubic Bipartite Graphs