Locally irregular edge-coloring of subcubic graphs Borut Lu zar M aria Macekov a Simona Rindo sov a

2025-05-02 0 0 518.88KB 17 页 10玖币
侵权投诉
Locally irregular edge-coloring
of subcubic graphs
Borut Luˇzar∗
, M´aria Macekov´a†
, Simona Rindoˇsov´a†
,
Roman Sot´ak†
, Katar´ına Srokov´a†
, Kenny ˇ
Storgel∗
October 11, 2022
Abstract
A graph is locally irregular if no two adjacent vertices have the same degree. A
locally irregular edge-coloring of a graph Gis such an (improper) edge-coloring that
the edges of any fixed color induce a locally irregular graph. Among the graphs
admitting a locally irregular edge-coloring, i.e., decomposable graphs, only one is
known to require 4 colors, while for all the others it is believed that 3 colors suffice.
In this paper, we prove that decomposable claw-free graphs with maximum degree
3, all cycle permutation graphs, and all generalized Petersen graphs admit a locally
irregular edge-coloring with at most 3 colors. We also discuss when 2 colors suffice
for a locally irregular edge-coloring of cubic graphs and present an infinite family
of cubic graphs of girth 4 which require 3 colors.
Keywords: locally irregular edge-coloring, locally irregular graph, subcubic graph, generalized
Petersen graph, cycle permutation graph
1 Introduction
A graph is locally irregular if no two adjacent vertices have the same degree. A locally
irregular edge-coloring (or a LIEC for short) of a graph Gis such an edge-coloring that
the edges of any fixed color induce a locally irregular graph. Since K2is not a locally
irregular graph, every LIEC is necessarily improper. Hence, there are graphs (e.g., odd
paths and odd cycles) that do not admit a LIEC. If a graph does admit a LIEC, we call it
decomposable. The smallest number of colors such that a decomposable graph Gadmits
a LIEC is called the locally irregular chromatic index and denoted by χ0
irr(G).
The locally irregular edge-coloring was introduced in 2015 by Baudon et al. [2] who
were motivated by the well-known (1-2-3)-Conjecture proposed in [6]. Since then, a
∗Faculty of Information Studies in Novo mesto, Slovenia. E-Mails: borut.luzar@gmail.com,
kennystorgel.research@gmail.com
†Faculty of Science, Pavol Jozef ˇ
Saf´arik University, Koˇsice, Slovakia,
E-Mails: {maria.macekova,roman.sotak}@upjs.sk,simona.rindosova@student.upjs.sk,
k.cekanova@gmail.com
1
arXiv:2210.04649v1 [math.CO] 10 Oct 2022
number of results were published. The first to establish a constant upper bound of 328
for the locally irregular chromatic index of decomposable graphs were Bensmail, Merker,
and Thomassen [4]. Their bound was further improved to 220 by Luˇzar, Przyby lo, and
Sot´ak [8], who combined the decomposition presented in [4] with a result on decomposition
of bipartite graphs to odd subgraphs presented in [7].
It turned out that only a few colors usually suffice for a LIEC of a decomposable graph,
and so Baudon et al. [2] conjectured that every decomposable graph admits a LIEC using
at most 3 colors. Their conjecture was just recently rejected by Sedlar and ˇ
Skrekovski [11]
who presented the graph H0with χ0
irr(H0) = 4 (see Figure 1).
Figure 1: The graph H0with χ0
irr(H0) = 4.
The graph H0is a cactus graph and after establishing that all decomposable cacti
except H0admit a LIEC with at most 3 colors [13] (see also [12]), Sedlar and ˇ
Skrekovski
proposed a revised conjecture.
Conjecture 1.1 (Sedlar and ˇ
Skrekovski [13]).For every connected decomposable graph
G, not isomorphic to H0, it holds that χ0
irr(G)≤3.
Regarding decomposable graphs admitting locally irregular edge-colorings using at
most 3 colors, it was shown that, e.g., k-regular graphs for k≥107[2], graphs with
minimum degree at least 1010 [9], trees [3], and unicyclic graphs [11] are such.
In this paper, we focus on graphs with maximum degree 3. In [8], the authors proved
the following.
Theorem 1.2 (Luˇzar, Przyby lo, and Sot´ak [8]).For every decomposable graph Gwith
maximum degree 3it holds that χ0
irr(G)≤4.
It remained an open question whether 3 colors are always sufficient. We partially
answer this by proving that the answer is affirmative for decomposable claw-free graphs
with maximum degree 3 in Section 3, and for cycle permutation graphs and generalized
Petersen graphs in Section 4.
We additionally study cubic graphs that do not admit a LIEC using at most 2 colors.
It is already known that every cubic bipartite graph Ghas χ0
irr(G)≤2 [2]. This motivated
us to investigate properties of (cubic) graphs which do not admit a LIEC with at most 2
colors. We present the results in Section 5.
2 Preliminaries
In this section, we present terminology, notation, and auxiliary results that we are using
in our proofs.
2
First, by a k-LIEC we refer to a locally irregular edge-coloring with at most kcolors.
For a k-LIEC σof G, we denote by di
σ(u) the number of edges incident with a vertex u
and colored with i; if the coloring σis clear from the context, we only write di(u). If two
vertices are incident with the same number of edges of some color, we say that they have
the same color degree.
Ak-vertex (a k+-vertex) is a vertex of degree k(at least k). A k-path P=v1, . . . , vk+1
is pendant in a graph Gif dG(v1) = 1, dG(vk+1)≥2, and dG(vi) = 2 for i= 2, . . . , k. By
ak-thread (a k+-thread) in a graph Gwe refer to a subgraph Tof Gisomorphic to the
k-path (a k+-path), in which all vertices have degree 2 also in G.
As described in [2], decomposable graphs have a very specific structure. In particular,
the graphs which are not decomposable are odd paths, odd cycles, and graphs from the
family Tdefined recursively as follows:
•the triangle is in T;
•every other graph in Tis constructed by taking an auxiliary graph Fwhich might
either be an even path or an odd path with a triangle glued to one end, then choosing
a graph G∈ T containing a triangle with at least one vertex vof degree 2, and
finally identifying vwith a vertex of degree 1 in F.
Note that all graphs in Thave maximum degree 3 and so any graph Gwith ∆(G)≥4 is
decomposable.
3 Claw-free graphs
In this section, we consider claw-free graphs with maximum degree 3 and show that if
such a graph is decomposable, then it admits a 3-LIEC.
Theorem 3.1. For every decomposable claw-free graph Gwith maximum degree 3it holds
that
χ0
irr(G)≤3.
Proof. We prove the theorem by contradiction. Let Gbe a minimal counterexample to the
theorem in terms of the number of edges; i.e., Gis a connected decomposable subcubic
claw-free graph with the minimum number of edges such that χ0
irr(G)>3. We first
establish several structural properties of G.
Claim 1. Gdoes not contain a pendant 2-path, i.e., in G, there is no edge uv with
d(u) = 1 and d(v) = 2.
Proof. Since Gis decomposable, by the definition of T, also the graph G0=G\ {u, v}is
decomposable. Thus, by the minimality, G0admits a 3-LIEC σ0which induces a partial
3-LIEC σof Gwith only the two edges incident with vbeing non-colored. Let wbe the
neighbor of vdistinct from u. Since wis incident with at most two colored edges, there
is a color α∈ {1,2,3}such that dα(w) = 0, and so we can set σ(vw) = σ(uv) = α, hence
extending σto all edges of G, a contradiction.
Claim 2. Gdoes not contain any 3-cycle incident with two 2-vertices.
3
Proof. Suppose the contrary and let C=v1v2v3be a 3-cycle with d(v1) = d(v2) = 2.
Clearly, d(v3) = 3; let ube the neighbor of v3, distinct from v1and v2. By the construction
of T, the graph G0=G\{v1, v2, v3}is decomposable and it admits a 3-LIEC, which induces
a partial 3-LIEC σof G, where the edges v1v2,v2v3,v1v3, and uv3are non-colored. We may
assume that d1(u) = 0. Then, we complete the coloring σby setting σ(uv3) = σ(v1v3) = 1
and σ(v1v2) = σ(v2v3) = 2, a contradiction.
Claim 3. Gdoes not contain any 4-cycle incident with two consecutive 2-vertices.
Proof. Suppose the contrary and let C=v1v2v3v4be a 4-cycle with d(v1) = d(v2) = 2.
Since ∆(G) = 3, we also assume that d(v3) = 3, and since Gis claw-free, d(v4) = 3 and
there is a vertex uadjacent to v3and v4.
Suppose that G0=G\ {v2, v3}is decomposable. Then, G0admits a 3-LIEC which
induces a partial 3-LIEC σof Gwhere only the edges v1v2,v2v3,v3v4, and uv3are non-
colored. We may assume that σ(v1v4) = σ(uv4) = 1 and d2(u) = 0. Hence, we can
complete the coloring by coloring the edges v1v2,v2v3,v3v4, and uv3with color 2, a
contradiction.
If G0is not decomposable, then G00 =G\ {v1, v2, v3}is decomposable and it admits a
3-LIEC which induces a partial 3-LIEC σof Gwhere the edges v1v2,v1v4,v2v3,v3v4, and
uv3are non-colored. Now, we may assume that σ(uv4) = 1 and d2(u) = 0. We complete
the coloring by coloring the edges v2v3,v3v4, and uv3with color 2, and the edges v1v2,
v1v4with 3, a contradiction.
Claim 4. Gdoes not contain any 2+-thread.
Proof. Suppose the contrary and let uand vbe adjacent 2-vertices in G. In particular,
without loss of generality, we choose the pair in such a way that the second neighbor of
uis a 3-vertex w. We label the vertices as depicted in Figure 2. By Claim 2, w6=z, and
since Gis claw-free, the two neighbors w1and w2of w, distinct from u, are adjacent. We
additionally assume that d(w1)≤d(w2).
u
v
z
w
w2
w1
w0
1
w0
2
1
Figure 2: A 2+-thread in Gis reducible. We depict vertices of nonspecified
degrees as empty circles and possibly nonexisting edges dashed, where the
vertices incident only to dashed edges may also not exist. Note also that
w0
1=w0
2is possible.
Let G0be the graph obtained from Gby contracting the edges uv and uw. By Claim 3,
zis not adjacent to w, and consequently, G0is a simple graph. Note that ∆(G0) = 3 and
by construction of T,G0is also decomposable. Moreover, by the minimality, G0admits
a 3-LIEC σ0which induces a partial 3-LIEC σof Gwhere only the edges uv and uw are
non-colored. Without loss of generality, we may assume that σ(vz) = 1. We show that
σalways extends to a 3-LIEC of Gby considering the cases regarding the colors of ww1
and ww2.
4
摘要：

Locallyirregularedge-coloringofsubcubicgraphsBorutLuzar*,MariaMacekova„,SimonaRindosova„,RomanSotak„,KatarnaSrokova„,KennyStorgel*October11,2022AbstractAgraphislocallyirregularifnotwoadjacentverticeshavethesamedegree.Alocallyirregularedge-coloringofagraphGissuchan(improper)edge-coloringtha...

展开>> 收起<<
Locally irregular edge-coloring of subcubic graphs Borut Lu zar M aria Macekov a Simona Rindo sov a.pdf

共17页,预览4页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：17 页 大小：518.88KB 格式：PDF 时间：2025-05-02

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 配电装置 动力学连接体 力的合成 高考理综 全宋诗作者索引 公务员考试
/ 17
评分 收藏
分享
立即下载
客服
关注