{ "labelLang" : "hun", "responseDate" : "2024-03-28 10:12", "content" : { "otype" : "BookChapter", "mtid" : 31436468, "status" : "VALIDATED", "published" : true, "unhandledTickets" : 0, "deleted" : false, "lastRefresh" : "2023-11-20T17:29:42.885+0000", "lastModified" : "2021-03-01T08:26:44.937+0000", "created" : "2020-08-26T16:08:43.404+0000", "creator" : { "otype" : "Admin", "mtid" : 565, "link" : "/api/admin/565", "label" : "WoS import (admin)", "familyName" : "WoS", "givenName" : "import", "published" : true, "snippet" : true }, "lastDuplumSearch" : "2023-11-20T17:28:35.693+0000", "validated" : "2023-11-20T17:28:35.789+0000", "validator" : { "otype" : "Admin", "mtid" : 521, "link" : "/api/admin/521", "label" : "Szuper Admin (admin)", "familyName" : "Szuper", "givenName" : "Admin", "published" : true, "snippet" : true }, "core" : false, "citation" : true, "publicationPending" : false, "type" : { "otype" : "PublicationType", "mtid" : 25, "link" : "/api/publicationtype/25", "label" : "Könyvrészlet", "code" : 25, "otypeName" : "BookChapter", "listPosition" : 2, "published" : true, "oldId" : 25, "snippet" : true }, "subType" : { "otype" : "SubType", "mtid" : 10000312, "link" : "/api/subtype/10000312", "label" : "Konferenciaközlemény (Könyvrészlet)", "name" : "Konferenciaközlemény", "nameEng" : "Conference paper", "docType" : { "otype" : "PublicationType", "mtid" : 25, "link" : "/api/publicationtype/25", "label" : "Könyvrészlet", "code" : 25, "otypeName" : "BookChapter", "listPosition" : 2, "published" : true, "oldId" : 25, "snippet" : true }, "listPosition" : 228, "published" : true, "oldId" : 10000312, "snippet" : true }, "category" : { "otype" : "Category", "mtid" : 1, "link" : "/api/category/1", "label" : "Tudományos", "published" : true, "oldId" : 1, "snippet" : true }, "languages" : [ { "otype" : "Language", "mtid" : 10002, "link" : "/api/language/10002", "label" : "Angol", "name" : "Angol", "nameEng" : "English", "published" : true, "oldId" : 2, "snippet" : true } ], "firstAuthor" : "Aboulker, Pierre", "authorships" : [ { "otype" : "PersonAuthorship", "mtid" : 92514680, "link" : "/api/authorship/92514680", "label" : "Aboulker, Pierre ✉", "listPosition" : 1, "share" : 0.0, "first" : true, "last" : false, "corresponding" : true, "familyName" : "Aboulker", "givenName" : "Pierre", "authorTyped" : true, "editorTyped" : false, "otherTyped" : false, "type" : { "otype" : "AuthorshipType", "mtid" : 1, "link" : "/api/authorshiptype/1", "label" : "Szerző", "code" : 0, "published" : true, "oldId" : 0, "snippet" : true }, "published" : false, "snippet" : true }, { "otype" : "PersonAuthorship", "mtid" : 92514681, "link" : "/api/authorship/92514681", "label" : "Bonnet, Edouard", "listPosition" : 2, "share" : 0.0, "first" : false, "last" : false, "corresponding" : false, "familyName" : "Bonnet", "givenName" : "Edouard", "authorTyped" : true, "editorTyped" : false, "otherTyped" : false, "type" : { "otype" : "AuthorshipType", "mtid" : 1, "link" : "/api/authorshiptype/1", "label" : "Szerző", "code" : 0, "published" : true, "oldId" : 0, "snippet" : true }, "published" : false, "snippet" : true }, { "otype" : "PersonAuthorship", "mtid" : 92514682, "link" : "/api/authorship/92514682", "label" : "Kim, Eun Jung", "listPosition" : 3, "share" : 0.0, "first" : false, "last" : false, "corresponding" : false, "familyName" : "Kim", "givenName" : "Eun Jung", "authorTyped" : true, "editorTyped" : false, "otherTyped" : false, "type" : { "otype" : "AuthorshipType", "mtid" : 1, "link" : "/api/authorshiptype/1", "label" : "Szerző", "code" : 0, "published" : true, "oldId" : 0, "snippet" : true }, "published" : false, "snippet" : true }, { "otype" : "PersonAuthorship", "mtid" : 92514683, "link" : "/api/authorship/92514683", "label" : "Sikora, Florian", "listPosition" : 4, "share" : 0.0, "first" : false, "last" : true, "corresponding" : false, "familyName" : "Sikora", "givenName" : "Florian", "authorTyped" : true, "editorTyped" : false, "otherTyped" : false, "type" : { "otype" : "AuthorshipType", "mtid" : 1, "link" : "/api/authorshiptype/1", "label" : "Szerző", "code" : 0, "published" : true, "oldId" : 0, "snippet" : true }, "published" : false, "snippet" : true } ], "title" : "Grundy Coloring & Friends, Half-Graphs, Bicliques", "identifiers" : [ { "otype" : "PublicationIdentifier", "mtid" : 17218854, "link" : "/api/publicationidentifier/17218854", "label" : "DOI: 10.4230/LIPIcs.STACS.2020.58", "source" : { "otype" : "PlainSource", "mtid" : 6, "link" : "/api/publicationsource/6", "label" : "DOI", "type" : { "otype" : "PublicationSourceType", "mtid" : 10001, "link" : "/api/publicationsourcetype/10001", "label" : "DOI", "mayHaveOa" : true, "published" : true, "snippet" : true }, "name" : "DOI", "nameEng" : "DOI", "linkPattern" : "https://doi.org/@@@", "publiclyVisible" : true, "published" : true, "oldId" : 6, "snippet" : true }, "validState" : "IDENTICAL", "idValue" : "10.4230/LIPIcs.STACS.2020.58", "realUrl" : "https://doi.org/10.4230/LIPIcs.STACS.2020.58", "published" : false, "snippet" : true }, { "otype" : "PublicationIdentifier", "mtid" : 17218855, "link" : "/api/publicationidentifier/17218855", "label" : "ISSN: 1868-8969", "source" : { "otype" : "PlainSource", "mtid" : 123, "link" : "/api/publicationsource/123", "label" : "ISSN", "type" : { "otype" : "PublicationSourceType", "mtid" : 10002, "link" : "/api/publicationsourcetype/10002", "label" : "Egyéb", "mayHaveOa" : false, "published" : true, "snippet" : true }, "name" : "ISSN", "nameEng" : "ISSN", "linkPattern" : "https://portal.issn.org/resource/ISSN/@@@", "publiclyVisible" : true, "published" : true, "oldId" : 123, "snippet" : true }, "validState" : "IDENTICAL", "idValue" : "1868-8969", "realUrl" : "https://portal.issn.org/resource/ISSN/1868-8969", "published" : false, "snippet" : true }, { "otype" : "PublicationIdentifier", "mtid" : 17218853, "link" : "/api/publicationidentifier/17218853", "label" : "WoS: 000521377300058", "source" : { "otype" : "PlainSource", "mtid" : 1, "link" : "/api/publicationsource/1", "label" : "WoS", "type" : { "otype" : "PublicationSourceType", "mtid" : 10003, "link" : "/api/publicationsourcetype/10003", "label" : "Indexelő adatbázis", "mayHaveOa" : false, "published" : true, "snippet" : true }, "name" : "WoS", "nameEng" : "WoS", "linkPattern" : "https://www.webofscience.com/wos/woscc/full-record/@@@", "publiclyVisible" : true, "published" : true, "oldId" : 1, "snippet" : true }, "validState" : "IDENTICAL", "idValue" : "000521377300058", "realUrl" : "https://www.webofscience.com/wos/woscc/full-record/000521377300058", "published" : false, "snippet" : true }, { "otype" : "PublicationIdentifier", "mtid" : 17218856, "link" : "/api/publicationidentifier/17218856", "label" : "Scopus: 85082113196", "source" : { "otype" : "PlainSource", "mtid" : 3, "link" : "/api/publicationsource/3", "label" : "Scopus", "type" : { "otype" : "PublicationSourceType", "mtid" : 10003, "link" : "/api/publicationsourcetype/10003", "label" : "Indexelő adatbázis", "mayHaveOa" : false, "published" : true, "snippet" : true }, "name" : "Scopus", "linkPattern" : "http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-@@@", "publiclyVisible" : true, "published" : true, "oldId" : 3, "snippet" : true }, "idValue" : "85082113196", "realUrl" : "http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85082113196", "published" : false, "snippet" : true } ], "internalId" : "UNSP 58", "firstPageOrInternalIdForSort" : "UNSP 58", "pageLength" : 18, "publishedYear" : 2020, "abstractText" : "The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order a, the smallest available color. The problem GRUNDY COLORING asks how many colors are needed for the most adversarial vertex ordering a , i.e., the maximum number of colors that the first-fit coloring requires over all possible vertex orderings. Since its inception by Grundy in 1939, GRUNDY COLORING has been examined for its structural and algorithmic aspects. A brute-force f (k)n(2k-1)-time algorithm for GRUNDY COLORING on general graphs is not difficult to obtain, where k is the number of colors required by the most adversarial vertex ordering. It was asked several times whether the dependency on k in the exponent of n can be avoided or reduced, and its answer seemed elusive until now. We prove that GRUNDY COLORING is K-t,K-t-hard arid the brute-force algorithm is essentially optimal under the Exponential Time Hypothesis, thus settling this question by the negative.The key ingredient in our W[1]-hardness proof is to use so-called hall-gmphs as a building block to transmit a color from one vertex to another. Leveraging the half-graphs, we also prove that b-CHROMATIC CORE is WW-hard, whose parameterized complexity was posed as an open question by Panolan et al. [JCSS '17]. A natural follow-up question is, how the parameterized complexity changes in the absence of (large) half-graphs. We establish fixed-parameter tractability on .K-t,K-t-free graphs for b-CHROMATIC CORE and PARTIAL GRUNDY COLORING, making a step toward answering this question. The key combinatorial lemma underlying the tractability result might be of independent interest.", "keywords" : [ { "otype" : "Keyword", "mtid" : 1068814, "link" : "/api/keyword/1068814", "label" : "Grundy coloring", "published" : true, "oldId" : 1068814, "snippet" : true }, { "otype" : "Keyword", "mtid" : 1174240, "link" : "/api/keyword/1174240", "label" : "Parameterized complexity", "published" : true, "oldId" : 1174240, "snippet" : true }, { "otype" : "Keyword", "mtid" : 2056108, "link" : "/api/keyword/2056108", "label" : "ETH lower bounds", "published" : true, "snippet" : true }, { "otype" : "Keyword", "mtid" : 2056109, "link" : "/api/keyword/2056109", "label" : "K-t,K-t-free graphs", "published" : true, "snippet" : true }, { "otype" : "Keyword", "mtid" : 2056110, "link" : "/api/keyword/2056110", "label" : "half-graphs", "published" : true, "snippet" : true } ], "digital" : true, "printed" : null, "sourceYear" : 2020, "foreignEdition" : true, "foreignLanguage" : true, "fullPublication" : true, "conferencePublication" : true, "nationalOrigin" : false, "missingAuthor" : false, "oaType" : "NONE", "oaCheckDate" : "2023-11-20", "oaFree" : false, "citationCount" : 0, "citationCountUnpublished" : 0, "citationCountWoOther" : 0, "independentCitCountWoOther" : 0, "doiCitationCount" : 0, "wosCitationCount" : 0, "scopusCitationCount" : 0, "independentCitationCount" : 0, "unhandledCitationCount" : 0, "citingPubCount" : 0, "independentCitingPubCount" : 0, "unhandledCitingPubCount" : 0, "citedPubCount" : 6, "citedCount" : 6, "hasCitationDuplums" : false, "userChangeableUntil" : "2021-05-30T07:10:51.953+0000", "directInstitutesForSort" : "", "ownerAuthorCount" : 6, "ownerInstituteCount" : 18, "directInstituteCount" : 0, "authorCount" : 4, "contributorCount" : 0, "book" : { "otype" : "Book", "mtid" : 31416432, "link" : "/api/publication/31416432", "label" : "Blaser M. 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). (2020)", "core" : false, "citation" : false, "publicationPending" : false, "type" : { "otype" : "PublicationType", "mtid" : 23, "link" : "/api/publicationtype/23", "label" : "Könyv", "code" : 23, "otypeName" : "Book", "listPosition" : 3, "published" : true, "oldId" : 23, "snippet" : true }, "subType" : { "otype" : "SubType", "mtid" : 10000144, "link" : "/api/subtype/10000144", "label" : "Konferenciakötet (Könyv)", "name" : "Konferenciakötet", "nameEng" : "Conference proceedings", "docType" : { "otype" : "PublicationType", "mtid" : 23, "link" : "/api/publicationtype/23", "label" : "Könyv", "code" : 23, "otypeName" : "Book", "listPosition" : 3, "published" : true, "oldId" : 23, "snippet" : true }, "listPosition" : 345, "published" : true, "oldId" : 10000144, "snippet" : true }, "category" : { "otype" : "Category", "mtid" : 1, "link" : "/api/category/1", "label" : "Tudományos", "published" : true, "oldId" : 1, "snippet" : true }, "languages" : [ { "otype" : "Language", "mtid" : 10002, "link" : "/api/language/10002", "label" : "Angol", "name" : "Angol", "nameEng" : "English", "published" : true, "oldId" : 2, "snippet" : true } ], "title" : "37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)", "identifiers" : [ ], "publishedAt" : [ { "otype" : "City", "mtid" : 14282, "link" : "/api/city/14282", "label" : "Wadern, Németország", "partOf" : { "otype" : "Country", "mtid" : 10011, "link" : "/api/country/10011", "label" : "Németország", "published" : true, "oldId" : 5, "snippet" : true }, "published" : true, "oldId" : 10005297, "snippet" : true } ], "publishedYear" : 2020, "foreignEdition" : true, "foreignLanguage" : true, "fullPublication" : false, "conferencePublication" : true, "published" : true, "snippet" : true }, "hasQualityFactor" : false, "link" : "/api/publication/31436468", "label" : "Aboulker Pierre et al. Grundy Coloring & Friends, Half-Graphs, Bicliques. (2020) Megjelent: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)", "template" : "