Simple view

Full metadata view

Authors

Statistics

First-fit coloring of incomparability graphs

2013
journal article
article
10.1137/110854394
Journal
SIAM Journal on Discrete Mathematics
25
Author
Bosek Bartłomiej

Krawczyk Tomasz

Matecki Grzegorz
Volume
27
Number
1
Pages
126-140
ISSN
0895-4801
eISSN
1095-7146
Language
English
Journal language
English
Abstract in English

One of the simplest heuristics for obtaining a proper coloring of a graph is the first-fit algorithm. First-fit visits each vertex of the graph in the specified order and assigns to every point the least possible number. Let be a class of incomparability graphs with bounded maximum clique size, closed under taking induced subgraphs. We prove that first-fit uses a bounded number of colors on the graphs in iff there is an incomparability graph of clique size not contained in .

Affiliation
Wydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznej
Scopus© citations
5
cris.lastimport.wos2024-04-10T00:40:05Z
dc.abstract.enOne of the simplest heuristics for obtaining a proper coloring of a graph is the first-fit algorithm. First-fit visits each vertex of the graph in the specified order and assigns to every point the least possible number. Let $\mathcal{G}$ be a class of incomparability graphs with bounded maximum clique size, closed under taking induced subgraphs. We prove that first-fit uses a bounded number of colors on the graphs in $\mathcal{G}$ iff there is an incomparability graph of clique size $2$ not contained in $\mathcal{G}$.pl
dc.affiliationWydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznejpl
dc.contributor.authorBosek, Bartłomiej - 114402 pl
dc.contributor.authorKrawczyk, Tomasz - 129445 pl
dc.contributor.authorMatecki, Grzegorz - 130386 pl
dc.date.accessioned2014-07-17T11:12:20Z
dc.date.available2014-07-17T11:12:20Z
dc.date.issued2013pl
dc.description.number1pl
dc.description.physical126-140pl
dc.description.volume27pl
dc.identifier.doi10.1137/110854394pl
dc.identifier.eissn1095-7146pl
dc.identifier.issn0895-4801pl
dc.identifier.urihttp://ruj.uj.edu.pl/xmlui/handle/item/107
dc.languageengpl
dc.language.containerengpl
dc.rights.licenceBez licencji otwartego dostępu
dc.subtypeArticlepl
dc.titleFirst-fit coloring of incomparability graphspl
dc.title.journalSIAM Journal on Discrete Mathematicspl
dc.typeJournalArticlepl
dspace.entity.typePublication
cris.lastimport.wos
2024-04-10T00:40:05Z
dc.abstract.enpl
One of the simplest heuristics for obtaining a proper coloring of a graph is the first-fit algorithm. First-fit visits each vertex of the graph in the specified order and assigns to every point the least possible number. Let $\mathcal{G}$ be a class of incomparability graphs with bounded maximum clique size, closed under taking induced subgraphs. We prove that first-fit uses a bounded number of colors on the graphs in $\mathcal{G}$ iff there is an incomparability graph of clique size $2$ not contained in $\mathcal{G}$.
dc.affiliationpl
Wydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznej
dc.contributor.authorpl
Bosek, Bartłomiej - 114402
dc.contributor.authorpl
Krawczyk, Tomasz - 129445
dc.contributor.authorpl
Matecki, Grzegorz - 130386
dc.date.accessioned
2014-07-17T11:12:20Z
dc.date.available
2014-07-17T11:12:20Z
dc.date.issuedpl
2013
dc.description.numberpl
1
dc.description.physicalpl
126-140
dc.description.volumepl
27
dc.identifier.doipl
10.1137/110854394
dc.identifier.eissnpl
1095-7146
dc.identifier.issnpl
0895-4801
dc.identifier.uri
http://ruj.uj.edu.pl/xmlui/handle/item/107
dc.languagepl
eng
dc.language.containerpl
eng
dc.rights.licence
Bez licencji otwartego dostępu
dc.subtypepl
Article
dc.titlepl
First-fit coloring of incomparability graphs
dc.title.journalpl
SIAM Journal on Discrete Mathematics
dc.typepl
JournalArticle
dspace.entity.type
Publication
Affiliations
Wydział Matematyki i Informatyki
Bosek, Bartłomiej
Krawczyk, Tomasz
Matecki, Grzegorz

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

Views
23
Views per month
Views per city
Des Moines
7
Philadelphia
3
Ashburn
2
Wroclaw
2
Boardman
1
Dublin
1
Venice
1

No access

No Thumbnail Available
Collections
Research publications