Coloring polygon visibility graphs and their generalizations

2023
journal article
article
cris.lastimport.wos2024-04-10T02:53:37Z
dc.abstract.enCurve pseudo-visibility graphs generalize polygon and pseudo- polygon visibility graphs and form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with clique number ω has chromatic number at most 3 · 4ω−1. The proof is carried through in the setting of ordered graphs; we identify two conditions satisfied by every curve pseudo- visibility graph (considered as an ordered graph) and prove that they are sufficient for the claimed bound. The proof is algorithmic: both the clique number and a coloring with the claimed number of colors can be computed in polynomial time.pl
dc.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.contributor.authorDavies, Jamespl
dc.contributor.authorKrawczyk, Tomasz - 129445 pl
dc.contributor.authorMcCarty, Rosepl
dc.contributor.authorWalczak, Bartosz - 114113 pl
dc.date.accessioned2023-03-29T07:33:36Z
dc.date.available2023-03-29T07:33:36Z
dc.date.issued2023pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.physical268-300pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume161pl
dc.identifier.doi10.1016/j.jctb.2023.02.010pl
dc.identifier.eissn1096-0902pl
dc.identifier.issn0095-8956pl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/309558
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 4.0 Międzynarodowa*
dc.rights.licenceCC-BY-NC-ND
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/legalcode.pl*
dc.share.typeinne
dc.subject.envisibility graphspl
dc.subject.enχ-boundednesspl
dc.subject.enpseudoline arrangementspl
dc.subject.enordered graphspl
dc.subtypeArticlepl
dc.titleColoring polygon visibility graphs and their generalizationspl
dc.title.journalJournal of Combinatorial Theory. Series Bpl
dc.typeJournalArticlepl
dspace.entity.typePublication
cris.lastimport.wos
2024-04-10T02:53:37Z
dc.abstract.enpl
Curve pseudo-visibility graphs generalize polygon and pseudo- polygon visibility graphs and form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with clique number ω has chromatic number at most 3 · 4ω−1. The proof is carried through in the setting of ordered graphs; we identify two conditions satisfied by every curve pseudo- visibility graph (considered as an ordered graph) and prove that they are sufficient for the claimed bound. The proof is algorithmic: both the clique number and a coloring with the claimed number of colors can be computed in polynomial time.
dc.affiliationpl
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.contributor.authorpl
Davies, James
dc.contributor.authorpl
Krawczyk, Tomasz - 129445
dc.contributor.authorpl
McCarty, Rose
dc.contributor.authorpl
Walczak, Bartosz - 114113
dc.date.accessioned
2023-03-29T07:33:36Z
dc.date.available
2023-03-29T07:33:36Z
dc.date.issuedpl
2023
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.physicalpl
268-300
dc.description.version
ostateczna wersja wydawcy
dc.description.volumepl
161
dc.identifier.doipl
10.1016/j.jctb.2023.02.010
dc.identifier.eissnpl
1096-0902
dc.identifier.issnpl
0095-8956
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/309558
dc.languagepl
eng
dc.language.containerpl
eng
dc.rights*
Udzielam licencji. Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 4.0 Międzynarodowa
dc.rights.licence
CC-BY-NC-ND
dc.rights.uri*
http://creativecommons.org/licenses/by-nc-nd/4.0/legalcode.pl
dc.share.type
inne
dc.subject.enpl
visibility graphs
dc.subject.enpl
χ-boundedness
dc.subject.enpl
pseudoline arrangements
dc.subject.enpl
ordered graphs
dc.subtypepl
Article
dc.titlepl
Coloring polygon visibility graphs and their generalizations
dc.title.journalpl
Journal of Combinatorial Theory. Series B
dc.typepl
JournalArticle
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
3
Views per month
Views per city
Geneva
1
Krakow
1
Downloads
krawczyk_et-al_coloring_polygon_visibility_graphs_and_their_generalizations_2023.pdf
2