Decomposing Split Graphs into Locally Irregular Graphs

被引:1
作者
Lintzmayer, C. N. [1 ]
Mota, G. O. [1 ]
Sambinelli, M. [2 ]
机构
[1] Fed Univ ABC, Ctr Math Comp & Cognit, Sao Paulo, Brazil
[2] Univ Sao Paulo, Inst Math & Stat, Sao Paulo, Brazil
基金
巴西圣保罗研究基金会;
关键词
Locally irregular; graph decomposition; split graphs; CHROMATIC INDEX;
D O I
10.1016/j.entcs.2019.08.053
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
A graph is locally irregular if any pair of adjacent vertices have distinct degrees. A locally irregular decomposition of a graph G is a decomposition of G into locally irregular subgraphs. A graph is said to be decomposable if it admits a locally irregular decomposition. In this paper we prove that any decomposable split graph whose clique has at least 10 vertices can be decomposed into at most three locally irregular subgraphs. Furthermore, we characterize those whose decomposition can be into one or two locally irregular subgraphs.
引用
收藏
页码:603 / 612
页数:10
相关论文
共 9 条
  • [1] HIGHLY IRREGULAR GRAPHS
    ALAVI, Y
    CHARTRAND, G
    CHUNG, FRK
    ERDOS, P
    GRAHAM, RL
    OELLERMANN, OR
    [J]. JOURNAL OF GRAPH THEORY, 1987, 11 (02) : 235 - 249
  • [2] [Anonymous], 2005, GRAPH THEORY
  • [3] On decomposing regular graphs into locally irregular subgraphs
    Baudon, O.
    Bensmail, J.
    Przybylo, J.
    Wozniak, M.
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2015, 49 : 90 - 104
  • [4] On the complexity of determining the irregular chromatic index of a graph
    Baudon, Olivier
    Bensmail, Julien
    Sopena, Eric
    [J]. JOURNAL OF DISCRETE ALGORITHMS, 2015, 30 : 113 - 127
  • [5] Bensmail J., 2018, ARXIV E PRINTS
  • [6] Decomposing graphs into a constant number of locally irregular subgraphs
    Bensmail, Julien
    Merker, Martin
    Thomassen, Carsten
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2017, 60 : 124 - 134
  • [7] Bondy J. A., 2008, GRADUATE TEXTS MATH
  • [8] New bounds for locally irregular chromatic index of bipartite and subcubic graphs
    Luzar, Borut
    Przybylo, Jakub
    Sotak, Roman
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (04) : 1425 - 1438
  • [9] Przybylo J, 2016, ELECTRON J COMB, V23