Simple view
Full metadata view
Authors
Statistics
Coloring polygon visibility graphs and their generalizations
Journal
Journal of Combinatorial Theory. Series B
140
Author
Davies James
Krawczyk Tomasz
McCarty Rose
Walczak Bartosz
Volume
161
Pages
268-300
ISSN
0095-8956
eISSN
1096-0902
Keywords in English
visibility graphs
χ-boundedness
pseudoline arrangements
ordered graphs
Language
English
Journal language
English
Abstract in English
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.
Affiliation
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
Scopus© citations
1
| cris.lastimport.wos | 2024-04-10T02:53:37Z | |
| dc.abstract.en | 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. | pl |
| dc.affiliation | Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej | pl |
| dc.contributor.author | Davies, James | pl |
| dc.contributor.author | Krawczyk, Tomasz - 129445 | pl |
| dc.contributor.author | McCarty, Rose | pl |
| dc.contributor.author | Walczak, Bartosz - 114113 | pl |
| dc.date.accessioned | 2023-03-29T07:33:36Z | |
| dc.date.available | 2023-03-29T07:33:36Z | |
| dc.date.issued | 2023 | pl |
| dc.date.openaccess | 0 | |
| dc.description.accesstime | w momencie opublikowania | |
| dc.description.physical | 268-300 | pl |
| dc.description.version | ostateczna wersja wydawcy | |
| dc.description.volume | 161 | pl |
| dc.identifier.doi | 10.1016/j.jctb.2023.02.010 | pl |
| dc.identifier.eissn | 1096-0902 | pl |
| dc.identifier.issn | 0095-8956 | pl |
| dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/309558 | |
| dc.language | eng | pl |
| dc.language.container | eng | pl |
| 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.en | visibility graphs | pl |
| dc.subject.en | χ-boundedness | pl |
| dc.subject.en | pseudoline arrangements | pl |
| dc.subject.en | ordered graphs | pl |
| dc.subtype | Article | pl |
| dc.title | Coloring polygon visibility graphs and their generalizations | pl |
| dc.title.journal | Journal of Combinatorial Theory. Series B | pl |
| dc.type | JournalArticle | pl |
| dspace.entity.type | Publication |
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
Wydział Matematyki i Informatyki
Krawczyk, Tomasz
Walczak, Bartosz
No affiliation
Davies, James
McCarty, Rose
* 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
12
Open Access
Loading...
