The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Kami mengkaji masalah mengubah satu (puncak) c-mewarna graf kepada graf lain dengan menukar hanya satu penetapan warna bucu pada satu masa, sambil pada setiap masa mengekalkan c-mewarna, di mana c menunjukkan bilangan warna. Masalah keputusan ini diketahui sebagai PSPACE-lengkap walaupun untuk graf dwipartit dan sebarang pemalar tetap c ≥ 4. Dalam kertas kerja ini, kami mengkaji masalah dari sudut pandangan kelas graf. Kami mula-mula menunjukkan bahawa masalah itu kekal PSPACE-lengkap untuk graf kord walaupun jika c ialah pemalar tetap. Kami kemudian menunjukkan bahawa, walaupun ketika c adalah sebahagian daripada input, masalahnya boleh diselesaikan dalam masa polinomial untuk beberapa kelas graf, seperti k-pokok dengan sebarang integer k ≥ 1, graf belah dan graf sempurna yang remeh.
Tatsuhiko HATANAKA
Tohoku University
Takehiro ITO
Tohoku University
Xiao ZHOU
Tohoku University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Tatsuhiko HATANAKA, Takehiro ITO, Xiao ZHOU, "The Coloring Reconfiguration Problem on Specific Graph Classes" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 3, pp. 423-429, March 2019, doi: 10.1587/transinf.2018FCP0005.
Abstract: We study the problem of transforming one (vertex) c-coloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a c-coloring, where c denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant c ≥ 4. In this paper, we study the problem from the viewpoint of graph classes. We first show that the problem remains PSPACE-complete for chordal graphs even if c is a fixed constant. We then demonstrate that, even when c is a part of input, the problem is solvable in polynomial time for several graph classes, such as k-trees with any integer k ≥ 1, split graphs, and trivially perfect graphs.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018FCP0005/_p
Salinan
@ARTICLE{e102-d_3_423,
author={Tatsuhiko HATANAKA, Takehiro ITO, Xiao ZHOU, },
journal={IEICE TRANSACTIONS on Information},
title={The Coloring Reconfiguration Problem on Specific Graph Classes},
year={2019},
volume={E102-D},
number={3},
pages={423-429},
abstract={We study the problem of transforming one (vertex) c-coloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a c-coloring, where c denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant c ≥ 4. In this paper, we study the problem from the viewpoint of graph classes. We first show that the problem remains PSPACE-complete for chordal graphs even if c is a fixed constant. We then demonstrate that, even when c is a part of input, the problem is solvable in polynomial time for several graph classes, such as k-trees with any integer k ≥ 1, split graphs, and trivially perfect graphs.},
keywords={},
doi={10.1587/transinf.2018FCP0005},
ISSN={1745-1361},
month={March},}
Salinan
TY - JOUR
TI - The Coloring Reconfiguration Problem on Specific Graph Classes
T2 - IEICE TRANSACTIONS on Information
SP - 423
EP - 429
AU - Tatsuhiko HATANAKA
AU - Takehiro ITO
AU - Xiao ZHOU
PY - 2019
DO - 10.1587/transinf.2018FCP0005
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2019
AB - We study the problem of transforming one (vertex) c-coloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a c-coloring, where c denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant c ≥ 4. In this paper, we study the problem from the viewpoint of graph classes. We first show that the problem remains PSPACE-complete for chordal graphs even if c is a fixed constant. We then demonstrate that, even when c is a part of input, the problem is solvable in polynomial time for several graph classes, such as k-trees with any integer k ≥ 1, split graphs, and trivially perfect graphs.
ER -