About: Partitions of graphs into cographs

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Partitions of graphs into cographs Goto Sponge Distinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	Cographs form the minimal family of graphs containing K-1 that is closed with respect to complementation and disjoint union. We discuss vertex partitions of graphs into the smallest number of cographs. We introduce a new parameter, calling the minimum order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show that both bounds are sharp for graphs with arbitrarily high girth. This provides an alternative proof to a result by Broere and Mynhardt. We show that any planar graph with girth at least 11 has a c-chromatic number at most two. We close with several remarks on computational complexity; in particular, that computing the c-chromatic number is NP-complete for planar graphs. Cographs form the minimal family of graphs containing K-1 that is closed with respect to complementation and disjoint union. We discuss vertex partitions of graphs into the smallest number of cographs. We introduce a new parameter, calling the minimum order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show that both bounds are sharp for graphs with arbitrarily high girth. This provides an alternative proof to a result by Broere and Mynhardt. We show that any planar graph with girth at least 11 has a c-chromatic number at most two. We close with several remarks on computational complexity; in particular, that computing the c-chromatic number is NP-complete for planar graphs. (en)
Title	Partitions of graphs into cographs Partitions of graphs into cographs (en)
skos:prefLabel	Partitions of graphs into cographs Partitions of graphs into cographs (en)
skos:notation	RIV/00216208:11320/10:10081040!RIV11-MSM-11320___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), Z(MSM0021620838)
http://linked.open...iv/cisloPeriodika	24
http://linked.open...vai/riv/dodaniDat	2011
http://linked.open...aciTvurceVysledku	Nešetřil, Jaroslav
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	278183
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/10:10081040
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	cographs; Partitions of graphs (en)
http://linked.open.../riv/klicoveSlovo	Partitions of graphs cographs
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[531E233A157C]
http://linked.open...i/riv/nazevZdroje	Discrete Mathematics
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science
http://linked.open...UplatneniVysledku	2010
http://linked.open...v/svazekPeriodika	310
http://linked.open...iv/tvurceVysledku	Nešetřil, Jaroslav Gimbel, John
http://linked.open...ain/vavai/riv/wos	000284251900001
http://linked.open...n/vavai/riv/zamer	Moderní metody, struktury a systémy informatiky
issn	0012-365X
number of pages	9 (xsd:int)
http://localhost/t...ganizacniJednotka	11320
is http://linked.open...avai/riv/vysledek of	Partitions of graphs into cographs Partitions of graphs into cographs Partitions of graphs into cographs

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 52 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software