| Autor: |
James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak |
| Jazyk: |
angličtina |
| Rok vydání: |
2023 |
| Předmět: |
|
| Popis: |
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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
