DC Field | Value | Language |
---|---|---|
dc.contributor.author | Choi, Ilkyoo | ko |
dc.contributor.author | Kim, Ringi | ko |
dc.contributor.author | Park, Boram | ko |
dc.date.accessioned | 2019-03-19T01:03:48Z | - |
dc.date.available | 2019-03-19T01:03:48Z | - |
dc.date.created | 2019-02-25 | - |
dc.date.issued | 2019-03 | - |
dc.identifier.citation | DISCRETE MATHEMATICS, v.342, no.3, pp.635 - 642 | - |
dc.identifier.issn | 0012-365X | - |
dc.identifier.uri | http://hdl.handle.net/10203/251473 | - |
dc.description.abstract | The chromatic number of a graph is the minimum k such that the graph has a proper k-coloring. There are many coloring parameters in the literature that are proper colorings that also forbid bicolored subgraphs. Some examples are 2-distance coloring, acyclic coloring, and star coloring, which forbid a bicolored path on three vertices, bicolored cycles, and a bicolored path on four vertices, respectively. This notion was first suggested by Crunbaum in 1973, but no specific name was given. We revive this notion by defining an H-avoiding k-coloring to be a proper k-coloring that forbids a bicolored subgraph H. When considering the class C of graphs with no F as an induced subgraph, it is not hard to see that every graph in C has bounded chromatic number if and only if F is a complete graph of size at most two. We study this phenomena for the class of graphs with no F as a subgraph for H-avoiding coloring. We completely characterize all graphs F where the class of graphs with no F as a subgraph has bounded H-avoiding chromatic number for a large class of graphs H. As a corollary, our main result implies a characterization of graphs F where the class of graphs with no F as a subgraph has bounded star chromatic number. We also obtain a complete characterization for the acyclic chromatic number. (C) 2018 Elsevier B.V. All rights reserved. | - |
dc.language | English | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.title | Characterization of forbidden subgraphs for bounded star chromatic number | - |
dc.type | Article | - |
dc.identifier.wosid | 000457821300004 | - |
dc.identifier.scopusid | 2-s2.0-85057780439 | - |
dc.type.rims | ART | - |
dc.citation.volume | 342 | - |
dc.citation.issue | 3 | - |
dc.citation.beginningpage | 635 | - |
dc.citation.endingpage | 642 | - |
dc.citation.publicationname | DISCRETE MATHEMATICS | - |
dc.identifier.doi | 10.1016/j.disc.2018.10.012 | - |
dc.contributor.nonIdAuthor | Choi, Ilkyoo | - |
dc.contributor.nonIdAuthor | Park, Boram | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Chromatic number | - |
dc.subject.keywordAuthor | Forbidden characterization | - |
dc.subject.keywordAuthor | Star coloring | - |
dc.subject.keywordAuthor | Acyclic coloring | - |
dc.subject.keywordPlus | GRAPHS | - |
dc.subject.keywordPlus | TREES | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.