{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q2223697","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q2223697","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q2223697","kernelVersion":"v1","immutable":true,"modified":"2026-01-25T22:44:54Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q2223697","name":"List 3-coloring graphs with no induced \\(P_6 + rP_3\\)","headline":"List 3-coloring graphs with no induced \\(P_6 + rP_3\\)","description":"scientific article; zbMATH DE number 7303848","url":"https://portal.mardi4nfdi.de/entity/Q2223697","datePublished":"2021-02-01","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q256974"},{"@id":"https://portal.mardi4nfdi.de/entity/Q322307"},{"@id":"https://portal.mardi4nfdi.de/entity/Q345122"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1637132"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q96582"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1007/S00453-020-00754-Y","url":"https://doi.org/10.1007/S00453-020-00754-Y"},"sameAs":["https://doi.org/10.1007/S00453-020-00754-Y"],"comment":"For graphs \\(G\\) and \\(H\\) we denote by \\(G+H\\) their disjoint union and \\(kH\\) represents \\(k\\) copies of \\(H\\). We also say that \\(G\\) is \\(H\\)-free if no induced subgraph of \\(G\\) is isomorphic to \\(H\\).  A function \\(f:V(G)\\rightarrow\\{1,2,3\\}\\) is a \\(3\\)-coloring if \\(f(u)\\neq f(v)\\) for every \\(uv\\in E(G)\\). The \\(3\\)-coloring problem is the problem of deciding if \\(g\\) has a \\(3\\)-coloring for a given graph \\(G\\).  A map \\(L\\) that assigns a subset of \\(\\{1,2,3\\}\\) to every vertex of \\(G\\) is called a \\(3\\)-list assignment for \\(G\\). For a \\(3\\)-list assignment \\(L\\) of \\(G\\) is \\(f:V(G)\\rightarrow\\{1,2,3\\}\\) a coloring of \\((G.L)\\) if \\(f\\) is a coloring of \\(G\\) and \\(f(v)\\in L(v)\\) for every \\(v\\in V(G)\\). Pair \\((G,L)\\) is colorable if \\((G,L)\\) has a coloring. The list \\(3\\)-coloring problem is the problem of deciding if \\((G,L)\\) is colorable.  The main result of this work is that the list \\(3\\)-coloring problem can be solved in polynomial time for a class of \\((P_6+rP_3)\\)-free graphs for every \\(r\\geq 0\\).  In contrast to this result, the authors show also that the \\(3\\)-coloring problem restricted to \\((P_5+P_2)\\)-free graphs is NP-hard.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q2252529"},{"@id":"https://portal.mardi4nfdi.de/entity/Q499486"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1786047"},{"@id":"https://portal.mardi4nfdi.de/entity/Q764301"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2182090"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2322884"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2978179"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1079363"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1323476"}]},"provenance":{"prov:generatedAtTime":"2026-01-25T22:44:54Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}