Subcoloring (original) (raw)
In graph theory, a subcoloring is an assignment of colors to a graph's vertices such that each color class induces a vertex disjoint union of cliques. That is, each color class should form a cluster graph. The subchromatic number χS(G) of a graph G is the fewest colors needed in any subcoloring of G. Subcoloring and subchromatic number were introduced by . Every proper coloring and cocoloring of a graph are also subcolorings, so the subchromatic number of any graph is at most equal to the cochromatic number, which is at most equal to the chromatic number.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a subcoloring is an assignment of colors to a graph's vertices such that each color class induces a vertex disjoint union of cliques. That is, each color class should form a cluster graph. The subchromatic number χS(G) of a graph G is the fewest colors needed in any subcoloring of G. Subcoloring and subchromatic number were introduced by . Every proper coloring and cocoloring of a graph are also subcolorings, so the subchromatic number of any graph is at most equal to the cochromatic number, which is at most equal to the chromatic number. Subcoloring is as difficult to solve exactly as coloring, in the sense that (like coloring) it is NP-complete. More specifically,the problem of determining whether a planar graph has subchromatic number at most 2 is NP-complete, even if it is a * triangle-free graph with maximum degree 4, * comparability graph with maximum degree 4, * line graph of a bipartite graph with maximum degree 4, * graph with girth 5. The subchromatic number of a cograph can be computed in polynomial time. For every fixed integer r, it is possible to decide in polynomial time whether the subchromatic number of interval and permutation graphs is at most r. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Subcoloring_graph.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p57 |
| dbo:wikiPageID | 702867 (xsd:integer) |
| dbo:wikiPageLength | 4435 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1082270386 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Electronic_Journal_of_Combinatorics dbr:Degree_(graph_theory) dbr:Induced_subgraph dbr:Information_Processing_Letters dbc:Graph_coloring dbr:Color dbr:Cluster_graph dbr:Girth_(graph_theory) dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:NP-complete dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Line_graph dbr:Clique_(graph_theory) dbr:Comparability_graph dbr:Triangle-free_graph dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Interval_graph dbr:Bipartite_graph dbr:Cocoloring dbr:Cograph dbr:Planar_graph dbr:Vertex_(graph_theory) dbr:Permutation_graph dbr:File:Subcoloring_graph.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt |
| dcterms:subject | dbc:Graph_coloring |
| gold:hypernym | dbr:Assignment |
| rdfs:comment | In graph theory, a subcoloring is an assignment of colors to a graph's vertices such that each color class induces a vertex disjoint union of cliques. That is, each color class should form a cluster graph. The subchromatic number χS(G) of a graph G is the fewest colors needed in any subcoloring of G. Subcoloring and subchromatic number were introduced by . Every proper coloring and cocoloring of a graph are also subcolorings, so the subchromatic number of any graph is at most equal to the cochromatic number, which is at most equal to the chromatic number. (en) |
| rdfs:label | Subcoloring (en) |
| owl:sameAs | freebase:Subcoloring wikidata:Subcoloring dbpedia-hu:Subcoloring https://global.dbpedia.org/id/fRQF |
| prov:wasDerivedFrom | wikipedia-en:Subcoloring?oldid=1082270386&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Subcoloring_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Subcoloring |
| is dbo:wikiPageRedirects of | dbr:Subchromatic_number |
| is dbo:wikiPageWikiLink of | dbr:List_of_graph_theory_topics dbr:Cluster_graph dbr:Graph_coloring dbr:Cocoloring dbr:Subchromatic_number |
| is foaf:primaryTopic of | wikipedia-en:Subcoloring |
