[vc_empty_space][vc_empty_space]
Backbone colorings along stars and matchings in split graphs: Their span is close to the chromatic number
Broersma H.a, Marchal B.b, Paulusma D.a, Salman A.N.M.c
a Department of Computer Science, Durham University, Science Laboratories, United Kingdom
b Department of Economics and Business Administration, Department of Quantitative Economics, University of Maastricht, Netherlands
c Department of Mathematics and Natural Sciences, Institut Teknologi Bandung Jalan, Indonesia
[vc_row][vc_column][vc_row_inner][vc_column_inner][vc_separator css=”.vc_custom_1624529070653{padding-top: 30px !important;padding-bottom: 30px !important;}”][/vc_column_inner][/vc_row_inner][vc_row_inner layout=”boxed”][vc_column_inner width=”3/4″ css=”.vc_custom_1624695412187{border-right-width: 1px !important;border-right-color: #dddddd !important;border-right-style: solid !important;border-radius: 1px !important;}”][vc_empty_space][megatron_heading title=”Abstract” size=”size-sm” text_align=”text-left”][vc_column_text]We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V;E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring for G and H is a proper vertex coloring V → {1, 2,⋯} of G in which the colors assigned to adjacent vertices in H di er by at least λ. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers. The main outcome of earlier studies is that the minimum number ‘ of colors, for which such colorings V → {1, 2, ⋯, l} exist, in the worst case is a factor times the chromatic number (forpath, tree, matching and star backbones). We show here that for split graphs and matching or star backbones, ‘ is at most a small additive constant (depending on λ) higher than the chromatic number. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on ‘ than the previously known bounds.[/vc_column_text][vc_empty_space][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][vc_empty_space][megatron_heading title=”Author keywords” size=”size-sm” text_align=”text-left”][vc_column_text][/vc_column_text][vc_empty_space][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][vc_empty_space][megatron_heading title=”Indexed keywords” size=”size-sm” text_align=”text-left”][vc_column_text]Backbone coloring,Matching,Split graph,Star[/vc_column_text][vc_empty_space][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][vc_empty_space][megatron_heading title=”Funding details” size=”size-sm” text_align=”text-left”][vc_column_text][/vc_column_text][vc_empty_space][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][vc_empty_space][megatron_heading title=”DOI” size=”size-sm” text_align=”text-left”][vc_column_text]https://doi.org/10.7151/dmgt.1437[/vc_column_text][/vc_column_inner][vc_column_inner width=”1/4″][vc_column_text]Widget Plumx[/vc_column_text][/vc_column_inner][/vc_row_inner][/vc_column][/vc_row][vc_row][vc_column][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][/vc_column][/vc_row]