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...
Main Authors: | , , , |
---|---|
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 |