Strong Chromatic Index of Outerplanar Graphs

The strong chromatic index <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mo>χ</mo><mi mathvariant="normal">s</mi><mo>′</mo></msubsup>&l...

Full description

Bibliographic Details
Main Authors: Ying Wang, Yiqiao Wang, Weifan Wang, Shuyu Cui
Format: Article
Language:English
Published: MDPI AG 2022-04-01
Series:Axioms
Subjects:
Online Access:https://www.mdpi.com/2075-1680/11/4/168
_version_ 1797436883841581056
author Ying Wang
Yiqiao Wang
Weifan Wang
Shuyu Cui
author_facet Ying Wang
Yiqiao Wang
Weifan Wang
Shuyu Cui
author_sort Ying Wang
collection DOAJ
description The strong chromatic index <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mo>χ</mo><mi mathvariant="normal">s</mi><mo>′</mo></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> of a graph <i>G</i> is the minimum number of colors needed in a proper edge-coloring so that every color class induces a matching in <i>G</i>. It was proved In 2013, that every outerplanar graph <i>G</i> with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>Δ</mo><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula> has <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mo>χ</mo><mi mathvariant="normal">s</mi><mo>′</mo></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≤</mo><mn>3</mn><mo>Δ</mo><mo>−</mo><mn>3</mn></mrow></semantics></math></inline-formula>. In this paper, we give a characterization for an outerplanar graph <i>G</i> to have <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mo>χ</mo><mi mathvariant="normal">s</mi><mo>′</mo></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><mn>3</mn><mo>Δ</mo><mo>−</mo><mn>3</mn></mrow></semantics></math></inline-formula>. We also show that if <i>G</i> is a bipartite outerplanar graph, then <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mo>χ</mo><mi mathvariant="normal">s</mi><mo>′</mo></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≤</mo><mn>2</mn><mo>Δ</mo></mrow></semantics></math></inline-formula>; and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mo>χ</mo><mi mathvariant="normal">s</mi><mo>′</mo></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><mn>2</mn><mo>Δ</mo></mrow></semantics></math></inline-formula> if and only if <i>G</i> contains a particular subgraph.
first_indexed 2024-03-09T11:10:01Z
format Article
id doaj.art-5d583ecfe1804b6bbf491f469131c6d2
institution Directory Open Access Journal
issn 2075-1680
language English
last_indexed 2024-03-09T11:10:01Z
publishDate 2022-04-01
publisher MDPI AG
record_format Article
series Axioms
spelling doaj.art-5d583ecfe1804b6bbf491f469131c6d22023-12-01T00:48:30ZengMDPI AGAxioms2075-16802022-04-0111416810.3390/axioms11040168Strong Chromatic Index of Outerplanar GraphsYing Wang0Yiqiao Wang1Weifan Wang2Shuyu Cui3School of Mathematics and Information Technology, Hebei Normal University of Science and Technology, Qinhuangdao 066004, ChinaSchool of Management, Beijing University of Chinese Medicine, Beijing 100029, ChinaDepartment of Mathematics, Zhejiang Normal University, Jinhua 321004, ChinaDepartment of Mathematics, Zhejiang Normal University, Jinhua 321004, ChinaThe strong chromatic index <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mo>χ</mo><mi mathvariant="normal">s</mi><mo>′</mo></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> of a graph <i>G</i> is the minimum number of colors needed in a proper edge-coloring so that every color class induces a matching in <i>G</i>. It was proved In 2013, that every outerplanar graph <i>G</i> with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>Δ</mo><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula> has <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mo>χ</mo><mi mathvariant="normal">s</mi><mo>′</mo></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≤</mo><mn>3</mn><mo>Δ</mo><mo>−</mo><mn>3</mn></mrow></semantics></math></inline-formula>. In this paper, we give a characterization for an outerplanar graph <i>G</i> to have <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mo>χ</mo><mi mathvariant="normal">s</mi><mo>′</mo></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><mn>3</mn><mo>Δ</mo><mo>−</mo><mn>3</mn></mrow></semantics></math></inline-formula>. We also show that if <i>G</i> is a bipartite outerplanar graph, then <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mo>χ</mo><mi mathvariant="normal">s</mi><mo>′</mo></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≤</mo><mn>2</mn><mo>Δ</mo></mrow></semantics></math></inline-formula>; and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mo>χ</mo><mi mathvariant="normal">s</mi><mo>′</mo></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><mn>2</mn><mo>Δ</mo></mrow></semantics></math></inline-formula> if and only if <i>G</i> contains a particular subgraph.https://www.mdpi.com/2075-1680/11/4/168strong edge-coloringstrong chromatic indexouterplanar graphbipartite graph
spellingShingle Ying Wang
Yiqiao Wang
Weifan Wang
Shuyu Cui
Strong Chromatic Index of Outerplanar Graphs
Axioms
strong edge-coloring
strong chromatic index
outerplanar graph
bipartite graph
title Strong Chromatic Index of Outerplanar Graphs
title_full Strong Chromatic Index of Outerplanar Graphs
title_fullStr Strong Chromatic Index of Outerplanar Graphs
title_full_unstemmed Strong Chromatic Index of Outerplanar Graphs
title_short Strong Chromatic Index of Outerplanar Graphs
title_sort strong chromatic index of outerplanar graphs
topic strong edge-coloring
strong chromatic index
outerplanar graph
bipartite graph
url https://www.mdpi.com/2075-1680/11/4/168
work_keys_str_mv AT yingwang strongchromaticindexofouterplanargraphs
AT yiqiaowang strongchromaticindexofouterplanargraphs
AT weifanwang strongchromaticindexofouterplanargraphs
AT shuyucui strongchromaticindexofouterplanargraphs