(2, 4)-Colorability of Planar Graphs Excluding Cycles with 3, 4, and 6 Vertices
A <i>defectivek-coloring</i> is a coloring on the vertices of a graph with colors <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>,</mo><mn>2</mn&...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-05-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/11/1762 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | A <i>defectivek-coloring</i> is a coloring on the vertices of a graph with colors <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>k</mi></mrow></semantics></math></inline-formula> where adjacent vertices may have the same color. A <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>d</mi><mn>1</mn></msub><mo>,</mo><msub><mi>d</mi><mn>2</mn></msub><mo>)</mo></mrow></semantics></math></inline-formula>-<i>coloring</i> of a graph <i>G</i> is a defective two-coloring such that each vertex colored by <i>i</i> has at most <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>d</mi><mi>i</mi></msub></semantics></math></inline-formula> adjacent vertices of the same color, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>=</mo><mn>1</mn><mo>,</mo><mn>2</mn></mrow></semantics></math></inline-formula>. A graph <i>G</i> is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>d</mi><mn>1</mn></msub><mo>,</mo><msub><mi>d</mi><mn>2</mn></msub><mo>)</mo></mrow></semantics></math></inline-formula>-<i>colorable</i> if it admits <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>d</mi><mn>1</mn></msub><mo>,</mo><msub><mi>d</mi><mn>2</mn></msub><mo>)</mo></mrow></semantics></math></inline-formula>-coloring. For planar graphs excluding cycles with three, four, and six vertices, Dross and Ochem, and additionally Sittitrai and Pimpasalee, have studied their defective 2-coloring. They showed that such graphs are <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>0</mn><mo>,</mo><mn>6</mn><mo>)</mo></mrow></semantics></math></inline-formula>- and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>3</mn><mo>,</mo><mn>3</mn><mo>)</mo></mrow></semantics></math></inline-formula>-colorable, respectively. We show in this work that these graphs are also <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>2</mn><mo>,</mo><mn>4</mn><mo>)</mo></mrow></semantics></math></inline-formula>-colorable. |
|---|---|
| ISSN: | 2227-7390 |