On 3-Coloring Circle Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10493555" target="_blank" >RIV/00216208:11320/24:10493555 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=agQuh34HRK" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=agQuh34HRK</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.7155/jgaa.v28i1.2991" target="_blank" >10.7155/jgaa.v28i1.2991</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On 3-Coloring Circle Graphs

Popis výsledku v původním jazyce

Given a graph G with a fixed vertex order PRECEDES, one obtains a circle graph H whose vertices are the edges of G and where two such edges are adjacent if and only if their endpoints are pairwise distinct and alternate in PRECEDES. Therefore, the problem of determining whether G has a k-page book embedding with spine order PRECEDES is equivalent to deciding whether H can be colored with k colors. Finding a k-coloring for a circle graph is known to be NP-complete for k &gt;= 4 [9] and trivial for k &lt;= 2. For k = 3, Unger (1992) claims an efficient algorithm that finds a 3-coloring in O(n log n) time, if it exists. Given a circle graph H, Unger&apos;s algorithm (1) constructs a 3-Sat formula Φ that is satisfiable if and only if H admits a 3-coloring and (2) solves Φ by a backtracking strategy that relies on the structure imposed by the circle graph. However, the extended abstract misses several details and Unger refers to his PhD thesis (in German) for details. In this paper we argue that Unger&apos;s algorithm for 3-coloring circle graphs is not correct and that 3-coloring circle graphs should be considered as an open problem. We show that step (1) of Unger&apos;s algorithm is incorrect by exhibiting a circle graph and its representation whose formula Φ is satisfiable but that is not 3-colorable. We further show that Unger&apos;s backtracking strategy for solving Φ in step (2) may produce incorrect results and give empirical evidence that it exhibits a runtime behaviour that is not consistent with the claimed running time.

Název v anglickém jazyce

On 3-Coloring Circle Graphs

Popis výsledku anglicky

Given a graph G with a fixed vertex order PRECEDES, one obtains a circle graph H whose vertices are the edges of G and where two such edges are adjacent if and only if their endpoints are pairwise distinct and alternate in PRECEDES. Therefore, the problem of determining whether G has a k-page book embedding with spine order PRECEDES is equivalent to deciding whether H can be colored with k colors. Finding a k-coloring for a circle graph is known to be NP-complete for k &gt;= 4 [9] and trivial for k &lt;= 2. For k = 3, Unger (1992) claims an efficient algorithm that finds a 3-coloring in O(n log n) time, if it exists. Given a circle graph H, Unger&apos;s algorithm (1) constructs a 3-Sat formula Φ that is satisfiable if and only if H admits a 3-coloring and (2) solves Φ by a backtracking strategy that relies on the structure imposed by the circle graph. However, the extended abstract misses several details and Unger refers to his PhD thesis (in German) for details. In this paper we argue that Unger&apos;s algorithm for 3-coloring circle graphs is not correct and that 3-coloring circle graphs should be considered as an open problem. We show that step (1) of Unger&apos;s algorithm is incorrect by exhibiting a circle graph and its representation whose formula Φ is satisfiable but that is not 3-colorable. We further show that Unger&apos;s backtracking strategy for solving Φ in step (2) may produce incorrect results and give empirical evidence that it exhibits a runtime behaviour that is not consistent with the claimed running time.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Graph Algorithms and Applications

ISSN

1526-1719

e-ISSN

1526-1719

Svazek periodika

28

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

14

Strana od-do

389-402

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85209207431